Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most L. For odd L ≥ 3 an asymptotic upper...
详细信息
ISBN:
(纸本)9781467377058
Consider the problem of packing Hamming balls of a given relative radius subject to the constraint that they cover any point of the ambient Hamming space with multiplicity at most L. For odd L ≥ 3 an asymptotic upper bound on the rate of any such packing is proven. The resulting bound improves the best known bound (due to Blinovsky' 1986) for rates below a certain threshold. The method is a superposition of the linear- programming idea of Ashikhmin, Barg and Litsyn (that was used previously to improve the estimates of Blinovsky for L = 2) and a Ramsey-theoretic technique of Blinovsky. As an application it is shown that for all odd L the slope of the rate-radius tradeoff is zero at zero rate.
This article continues the recent investigation of combinatorial joint source-channel coding. For the special case of a binary source and channel subject to distortion measured by Hamming distance, the lower (converse...
详细信息
This article continues the recent investigation of combinatorial joint source-channel coding. For the special case of a binary source and channel subject to distortion measured by Hamming distance, the lower (converse) bounds on achievable source distortion are improved for all values of channel noise. Operational duality between coding with bandwidth expansion factors ρ and 1 over ρ is established. Although the exact value of the asymptotic noise-distortion tradeoff curve is unknown (except at ρ = 1), some initial results on inter-relations between these curves for different values of ρ are shown and lead to statements about monotonicity and continuity in ρ.
We consider the quickest flow problem in dynamic networks with a single source s and a single sink t: given an amount of flow F, find the minimum time needed to send it from s to t, and the corresponding optimal flow ...
详细信息
ISBN:
(纸本)9781510813311
We consider the quickest flow problem in dynamic networks with a single source s and a single sink t: given an amount of flow F, find the minimum time needed to send it from s to t, and the corresponding optimal flow over time. We introduce new mathematical formulations and derive optimality conditions for the quickest flow problem. Based on the optimality conditions, we develop a new costscaling algorithm that leverages the parametric nature of the problem. The algorithm solves the quickest flow problem with integer arc costs in O(nm log(n~2/m) log(nC)) time, where n, m, and C are the number of nodes, arcs, and the maximum arc cost, respectively. Our algorithm runs in the same time bound as the costscaling algorithm by Goldberg and Tarjan [10, 11] for solving the min-cost flow problem. This result shows for the first time that the quickest flow problem can be solved within the same time bound as one of the fastest algorithms for the min-cost flow problem. As a consequence, our algorithm will remain one of the fastest unless the quickest flow problem can be shown to be simpler than the min-cost flow problem.
We present a new approach to the design of smooth trajectories for quadrotor unmanned aerial vehicles (UAVs), which are free of collisions with obstacles along their entire length. To avoid the non-convex constraints ...
详细信息
We present a new approach to the design of smooth trajectories for quadrotor unmanned aerial vehicles (UAVs), which are free of collisions with obstacles along their entire length. To avoid the non-convex constraints normally required for obstacle-avoidance, we perform a mixed-integer optimization in which polynomial trajectories are assigned to convex regions which are known to be obstacle-free. Prior approaches have used the faces of the obstacles themselves to define these convex regions. We instead use IRIS, a recently developed technique for greedy convex segmentation [1], to pre-compute convex regions of safe space. This results in a substantially reduced number of integer variables, which improves the speed with which the optimization can be solved to its global optimum, even for tens or hundreds of obstacle faces. In addition, prior approaches have typically enforced obstacle avoidance at a finite set of sample or knot points. We introduce a technique based on sums-of-squares (SOS) programming that allows us to ensure that the entire piecewise polynomial trajectory is free of collisions using convex constraints. We demonstrate this technique in 2D and in 3D using a dynamical model in the Drake toolbox for Matlab [2].
Summary form only given. As massively distributed storage becomes the norm in cloud networks, they contend with new vulnerabilities imputed by the presence of data in different, possibly untrusted nodes. In this talk,...
Summary form only given. As massively distributed storage becomes the norm in cloud networks, they contend with new vulnerabilities imputed by the presence of data in different, possibly untrusted nodes. In this talk, we consider two such types of vulnerabilities. The first one is the risk posed to data stored at nodes that are untrusted. We show that coding alone can be substituted to encryption, with coded portions of data in trusted nodes acting as keys for coded data in untrusted ones. In general, we may interpret keys as representing the size of the list over which an adversary would need to generate guesses in order to recover the plaintext, leading to a natural connection between list decoding and secrecy. Under such a model, we show that algebraic block maximum distance separable (MDS) codes can be constructed so that lists satisfy certain secrecy criteria, which we define to generalize common perfect secrecy and weak secrecy notions. The second type of vulnerability concerns the risk of passwords' being guessed over some nodes storing data, as illustrated by recent cloud attacks. In this domain, the use of guesswork as a metric shows that the dominant effect on vulnerability is not necessarily from a single node, but that it varies in time according to the number of guesses issued. We also introduce the notion of inscrutability, as the growth rate of the average number of probes that an attacker has to make, one at a time, using his best strategy, until he can correctly guess one or more secret strings from multiple randomly chosen strings. Joint work with Ahmad Beirami, Joao Barros, Robert Calderbank, Mark Christiansen, Ken Duffy, Flavio du Pin Calmon, Luisa Lima, Paulo Oliveira, Stefano Tessaro, Mayank Varia, Tiago Vinhoza, Linda Zeger.
Sepsis, which occurs when an infection leads to a systemic inflammatory response, is believed to contribute to one in two to three hospital deaths in the United States. Using the Multiparameter Intelligent Monitoring ...
详细信息
ISBN:
(纸本)9781424492695
Sepsis, which occurs when an infection leads to a systemic inflammatory response, is believed to contribute to one in two to three hospital deaths in the United States. Using the Multiparameter Intelligent Monitoring in Intensive Care (MIMIC II) database of electronic medical records from Boston's Beth Israel Deaconess Medical Center (BIDMC), we worked to characterize sepsis at BIDMC's intensive care units. Additionally, we developed a real-time algorithm to stratify patients with infectious complaints into different risk categories for progressing to septic shock. From time series of heart rate and arterial blood pressure, as well as estimates of cardiac output and total peripheral resistance, we developed a variety of classifiers to predict high serum lactate levels, a proxy for hypoperfusion and imminent circulatory shock. The records from 146 patients met our selection criteria. In discriminating patients whose measured serum lactate stays below 2.5 mmol/L from those whose value drifts above, the best of our classifiers perform with area under the receiver operating characteristic exceeding 0.8 on test data.
We report the first results from a combinatorial design effort focused on new OLED emitters that exploit thermally-activated delayed fluorescence. Using quantum chemistry and machine learning techniques to prune a poo...
详细信息
Atrial fibrillation (AFib) is diagnosed by analysis of the morphological and rhythmic properties of the electrocardiogram. It was recently shown that accurate detection of AFib is possible using beat-to-beat interval ...
详细信息
Atrial fibrillation (AFib) is diagnosed by analysis of the morphological and rhythmic properties of the electrocardiogram. It was recently shown that accurate detection of AFib is possible using beat-to-beat interval variations. This raises the question of whether AFib detection can be performed using a pulsatile waveform such as the Photoplethysmogram (PPG). The recent explosion in use of recreational and professional ambulatory wrist-based pulse monitoring devices means that an accurate pulse-based AFib screening algorithm would enable large scale screening for silent or undiagnosed AFib, a significant risk factor for multiple diseases. We propose a noise-resistant machine learning approach to detecting AFib from noisy ambulatory PPG recorded from the wrist using a modern research watch-based wearable device (the Samsung Simband). Ambulatory pulsatile and movement data were recorded from 46 subjects, 15 with AFib and 31 non symptomatic. Single channel electrocardiogram (ECG), multi-wavelength PPG and tri-axial accelerometry were recorded simultaneously at 128 Hz from the non-dominant wrist using the Simband. Recording lengths varied from 3.5 to 8.5 minutes. Pulse (beat) detection was performed on the PPG waveforms, and eleven features were extracted based on beat-to-beat variability and waveform signal quality. Using 10-fold cross validation, an accuracy of 95 % on out-of-sample data was achieved, with a sensitivity of 97%, specificity of 94%, and an area under the receiver operating curve (AUROC) of 0.99. The described approach provides a noise-resistant, accurate screening tool for AFib from PPG sensors located in an ambulatory wrist watch. To our knowledge this is the first study to demonstrate an algorithm with a high enough accuracy to be used in general population studies that does not require an ambulatory Holter electrocardiographic monitor.
As massively distributed storage becomes the norm in cloud networks, they contend with new vulnerabilities imputed by the presence of data in different, possibly untrusted nodes. In this talk, we consider two such typ...
As massively distributed storage becomes the norm in cloud networks, they contend with new vulnerabilities imputed by the presence of data in different, possibly untrusted nodes. In this talk, we consider two such types of vulnerabilities. The first one is the risk posed to data stored at nodes that are untrusted. We show that coding alone can be substituted to encryption, with coded portions of data in trusted nodes acting as keys for coded data in untrusted ones. In general, we may interpret keys as representing the size of the list over which an adversary would need to generate guesses in order to recover the plaintext, leading to a natural connection between list decoding and secrecy. Under such a model, we show that algebraic block maximum distance separable (MDS) codes can be constructed so that lists satisfy certain secrecy criteria, which we define to generalize common perfect secrecy and weak secrecy notions. The second type of vulnerability concerns the risk of passwords' being guessed over some nodes storing data, as illustrated by recent cloud attacks. In this domain, the use of guesswork as a metric shows that the dominant effect on vulnerability is not necessarily from a single node, but that it varies in time according to the number of guesses issued. We also introduce the notion of inscrutability, as the growth rate of the average number of probes that an attacker has to make, one at a time, using his best strategy, until he can correctly guess one or more secret strings from multiple randomly chosen strings. Joint work with Ahmad Beirami, Joao Barros, Robert Calderbank, Mark Christiansen, Ken Duffy, Flavio du Pin Calmon, Luisa Lima, Paulo Oliveira, Stefano Tessaro, Mayank Varia, Tiago Vinhoza, Linda Zeger.
High-performance Model-Code Separation (MCS) architectures for lossless compression are practically viable with graphical message-passing in the decoder. This paper extends separation architectures to lossy compressio...
详细信息
High-performance Model-Code Separation (MCS) architectures for lossless compression are practically viable with graphical message-passing in the decoder. This paper extends separation architectures to lossy compression by constructing model-free but semantics-aware encoders and contributes a new inference-friendly low-density hashing quantizer (LDHQ) to support decoding.
暂无评论