113 research outputs found
Tight Bounds for Communication-Assisted Agreement Distillation
No full textSuppose Alice holds a uniformly random string X in {0,1}^N and Bob holds a noisy version Y of X where each bit of X is flipped independently with probability epsilon in [0,1/2]. Alice and Bob would like to extract a common random string of min-entropy at least k. In this work, we establish the communication versus success probability trade-off for this problem by giving a protocol and a matching lower bound (under the restriction that the string to be agreed upon is determined by Alice's input X). Specifically, we prove that in order for Alice and Bob to agree on a common string with probability 2^{-gamma k} (gamma k >= 1), the optimal communication (up to o(k) terms, and achievable for large N) is precisely (C *(1-gamma) - 2 * sqrt{ C * (1-C) gamma}) * k, where C := 4 * epsilon * (1-epsilon). In particular, the optimal communication to achieve Omega(1) agreement probability approaches 4 * epsilon * (1-epsilon) * k.
We also consider the case when Y is the output of the binary erasure channel on X, where each bit of Y equals the corresponding bit of X with probability 1-epsilon and is otherwise erased (that is, replaced by a "?"). In this case, the communication required becomes (epsilon * (1-gamma) - 2 * sqrt{ epsilon * (1-epsilon) * gamma}) * k. In particular, the optimal communication to achieve Omega(1) agreement probability approaches epsilon * k, and with no communication the optimal agreement probability approaches 2^{- (1-sqrt{1-epsilon})/(1+sqrt{1-epsilon}) * k}.
Our protocols are based on covering codes and extend the approach of (Bogdanov and Mossel, 2011) for the zero-communication case. Our lower bounds rely on hypercontractive inequalities. For the model of bit-flips, our argument extends the approach of (Bogdanov and Mossel, 2011) by allowing communication; for the erasure model, to the best of our knowledge the needed hypercontractivity statement was not studied before, and it was established (given our application) by (Nair and Wang 2015). We also obtain information complexity lower bounds for these tasks, and together with our protocol, they shed light on the recently popular "most informative Boolean function" conjecture of Courtade and Kumar
An improved bound on the zero-error list-decoding capacity of the 4/3 channel
No full textWe prove a new, improved upper bound on the size of codes C ⊆{1, 2, 3, 4}n with the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we show that such a code has size at most 26n/19 +o(n), or equivalently has rate bounded by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlos, 1984) and (Korner and Marton, 1988). The context for this problem is two-fold: zero-error list decoding capacity, where such codes give a way to communicate with no error on the “4/3 channel” when list-of-3 decoding is employed, and perfect hashing, where such codes give a perfect hash family of size n mapping C to {1, 2, 3, 4}
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
No full textMotivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O (log A) times the optimum, A being the maximum degree of the input network. This is best-possible if NP not subset of DTIME[n(O(log log n))] and if the processors are required to run in polynomial-time. We then show how to construct dominating sets that have the above properties, as well as the "low stretch" property that any two adjacent nodes in the network have their dominators at a distance of at most O (log n) in the output network. (Given a dominating set S, a dominator of a vertex u is any nu epsilon S such. that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal. (c) 2005 Elsevier Inc. All rights reserved
A fast approximation algorithm for solving the complete set packing problem
No full textWe study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature
Set membership with two bit probes
No full textWe will consider the bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to answer membership queries of the form Is x in S? by adaptively probing the bit vector at t places. Let s(m,n,t) be the minimum number of bits of storage needed for such a scheme. Alon and Feige showed that for t=2 (two bit probes), such schemes can be obtained from dense graphs with large girth. In particular, they showed that for n \u3c \log m,
s(m,n,2) = O(m n \log((\log m) / n) / \log m).
We improve their analysis and obtain a better upper bound and a corresponding lower bound.
Upper bound: There is a constant C\u3e0, such that for all large m,
s(m,n,2) \leq C \cdot m^{1-\frac{1}{(4n+1)}}.
Lower bound: There is a constant D\u3e0, such that for n\geq 4 and all large m, we have
s(m,n,2) \geq D \cdot m^{1-\frac{1}{\lfloor n/4 \rfloor}}.
(This is joint work with Mohit Garg.)
Download the attached PDF to see the abstract with proper math formatting
Flexibility in adaptation planning: When, where and how to include flexibility for increasing urban flood resilience
No full textThe magnitude and urgency of the need to adapt to climate change is such that addressing it has been taken up by the United Nations as one of the sustainable development goals - Goal 13 (SDG13) in 2015. SDG13 emphasises the need to strengthen resilience and adaptive capacity to climate related hazards and natural disasters. Coping with urban floods is one of the major needs of climate adaptation, where integration of climate change responses into flood risk management policies, strategies and planning at international, national, regional and local levels is now the norm. However, much of this integration lacks effectiveness or real commitment from stakeholders involved in adaptation planning and implementation. Hence this research has focused on integrating flexibility based adaptation responses into an urban flood risk management context. The research has synthesised flexible adaptation practices from several disciplines including information technology, automobile and aerospace manufacturing. The outcomes of the research are brought together in a framework for structuring local adaptation responses and an adaptation planning process based on flexibility concepts. The outcomes provide a way to assist with the identification of the appropriate nature and type of flexibility required; where flexibility can best be incorporated; and when is the most appropriate time to implement the flexible adaptation responses in the context of urban flooding.Dissertation submitted in fulfilment of the requirements of the Board for Doctorates of Delft University of Technology and of the Academic Board of the UNESCO-IHE Institute for Water Education.Hydraulic Structures and Flood Ris
A Direct Sum Theorem in Communication Complexity via Message Compression
No full textWe prove lower bounds for the direct sum problemfor two-party bounded error randomisedmultipleround communication protocols. Our proofs use the notion of information cost of a protocol, as defined by Chakrabarti et al. [CSWY01] and refined further by Bar-Yossef et al. [BJKS02]. Our main technical result is a 'compression' theoremsaying that, for any probability distribution μ over the inputs, a k-round private coin bounded error protocol for a function ƒ with information cost c can be converted into a kround deterministic protocol for ƒ with bounded distributional error and communication cost O(kc). We prove this result using a substate theorem about relative entropy and a rejection sampling argument. Our direct sum result follows from this 'compression' result via elementary information theoretic arguments. We also consider the direct sumproblemin quantumcommunication. Using a probabilistic argument, we show thatmessages cannot be compressed in thismanner even if they carry small information. Hence, new techniques may be necessary to tackle the direct sum problem in quantum communication
On converting CNF to DNF
No full textAbstractWe study how big the blow-up in size can be when one switches between the CNF and DNF representations of Boolean functions. For a function f:{0,1}n→{0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0⩽m⩽2n-1, let dnfsize(m,n) be the maximum dnfsize(f) for a function f:{0,1}n→{0,1} with cnfsize(f)⩽m. We show that there are constants c1,c2⩾1 and ε>0, such that for all large n and all m∈[1εn,2εn], we have2n-c1(n/log(m/n))⩽dnfsize(m,n)⩽2n-c2(n/log(m/n)).In particular, when m is the polynomial nc, we get dnfsize(nc,n)=2n-θ(c-1(n/logn))
Bounded model checking of multi-threaded c programs via lazy sequentialization
No full textBounded model checking (BMC) has successfully been used for many practical program verification problems, but concurrency still poses a challenge. Here we describe a new approach to BMC of sequentially consistent C programs using POSIX threads. Our approach first translates a multi-threaded C program into a nondeterministic sequential C program that preserves reachability for all round-robin schedules with a given bound on the number of rounds. It then re-uses existing high-performance BMC tools as backends for the sequential verification problem. Our translation is carefully designed to introduce very small memory overheads and very few sources of nondeterminism, so that it produces tight SAT/SMT formulae, and is thus very effective in practice: our prototype won the concurrency category of SV-COMP14. It solved all verification tasks successfully and was 30x faster than the best tool with native concurrency handling.<br/
The Communication Complexity of Pointer Chasing
No full textAbstractWe study the k-round two-party communication complexity of the pointer chasing problem for fixed k. C. Damm, S. Jukna and J. Sgall (1998, Comput. Complexity7, 109–127) showed an upper bound of O(nlog(k−1)n) for this problem. We prove a matching lower bound; this improves the lower bound of Σ(n) shown by N. Nisan and A. Widgerson (1993, SIAM J. Comput.22, 211–219), and yields a corresponding improvement in the hierarchy results derived by them and by H. Klauck (1998, in “Proceeding of the Thirteenth Annual IEEE Conference on Computational Complexity,” pp. 141–152) for bounded-depth monotone circuits. We consider the bit version of this problem, and show upper and lower bounds. This implies that there is an abrupt jump in complexity, from linear to superlinear, when the number of rounds is reduced to k/2 or less. We also consider the s-paths version (originally studied by H. Klauck) and show an upper bound. The lower bounds are based on arguments using entropy. One of the main contributions of this work is a transfer lemma for distributions with high entropy; this should be of independent interest
- …
