We consider the communication complexity of the graph connectivity problem, where the edges of an n-vertex undirected graph G are distributed between two parties Alice and Bob, who are then required to communicate to determine if G is connected. We show that in any randomized protocol with two-rounds of communication, Alice and Bob must exchange Ω(nlog n) bits; such a lower bound for one-round protocols was shown by Sun and Woodruff (APPROX/RANDOM 2015). A one-round deterministic protocol, where Alice sends O(n log n) bits and Bob determines the answer, was observed by Hajnal, Maass and Turan (STOC 1988); they also showed a matching lower bound of Ω(n log n) bits for deterministic protocols with unbounded rounds of communication. For randomized protocols, a reduction from the set disjointness problem due to Babai, Frankl and Simon (FOCS 1986) implies a randomized lower bound of Ω(n) even with unbounded rounds of communication. Whether this lower bound can be improved to Ω(n log n) has been an outstanding open question, whose algorithmic implications were recently emphasized by Apers, Efron, Gawrychowski, Lee, Mukopadhyay and Nanongkai (FOCS 2022). Our lower bound for randomized two-round protocols is based on a reduction from a restricted version of the two-player pointer chasing problem originally studied by Papadimitriou and Sipser (JCSS 1984). Using this reduction, we show an ω(n) lower bounds on graph connectivity for any constant number of rounds by extending deterministic lower bounds shown by Ponzio, Radhakrishnan and Venkatesh (JCSS 2001) to the randomized setting.

A classic result of Nisan [SICOMP ’91] states that the deterministic decision tree *depth* complexity of every total Boolean function is at most the cube of its randomized decision tree *depth* complexity. The question whether randomness helps in significantly reducing the *size* of decision trees appears not to have been addressed. We show that the logarithm of the deterministic decision tree size complexity of every total Boolean function on n input variables is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, ignoring a polylogarithmic factor in the input size.

We consider the following problem: Given a set S of at most n elements from a universe of size m, represent it in memory as a bit string so that membership queries of the form "Is x in S?" can be answered by making at most t probes into the bit string. Let s(m,n,t) be the minimum number of bits needed by any such scheme. We obtain new upper bounds for s(m,n,t=2), which match or improve all the previously known bounds. We also consider the quantum version of this problem and obtain improved upper bounds.

Let$\mathcal {X}= \{x_{1},x_{2},\ldots, x_{q}\}$and let$n(m,q,\ell)$be the smallest$n$for which there is a code$C \subseteq \mathcal {X} ^{n}$of$m$elements such that for every list$w_{1}, w_{2}, \ldots, w_{\ell +1}$of distinct codewords from$C$, there is a coordinate$j \in [n]$such that$\{w_{1}[j], w_{2}[j], \ldots, w_{\ell +1}[j]\} = \mathcal {X}$. We show that there is a constant$A>0$such that for$\epsilon < 1/5$, for all large$q$and large enough$m$($m>q^{5}$), we have$n(m,q, \lceil \epsilon q\ln {q}\rceil) \geq \exp {(Aq^{1-5\epsilon })}\log _{2}{m}$. This bound has consequences for the zero-error list-decoding capacity of the$q/(q-1)$channel studied by Elias (1988). Our result implies that for$A$and$\epsilon $as above, the zero-error list-decoding capacity of the$q/(q-1)$channel with list-size$\epsilon q\ln {q}$is at most$\exp (-Aq^{1-5\epsilon })$, that is, it falls exponentially as$q$increases. This confirms a conjecture of Chakrabortyet al.(2006).

The following is a classical question of Erdős (Nordisk Matematisk Tidskrift, 1963) and of Erdős and Lovász (Colloquia Mathematica Societatis János Bolyai, vol. 10, 1975). Given a hypergraph ℱ with minimum edge-size k, what is the largest function g(k) such that if the expected number of monochromatic edges in ℱ is at most g(k) when the vertices of ℱ are colored red and blue randomly and independently, then we are guaranteed that ℱ is two-colorable? Duraj, Gutowski and Kozik (ICALP 2018) have shown that g(k) ≥ Ω(log k). On the other hand, if ℱ is k-uniform, the lower bound on g(k) is much higher: g(k) ≥ Ω(√{k / log k}) (Radhakrishnan and Srinivasan, Rand. Struct. Alg., 2000). In order to bridge this gap, we define a family of locally-almost-uniform hypergraphs, for which we show, via the randomized algorithm of Cherkashin and Kozik (Rand. Struct. Alg., 2015), that g(k) can be much higher than Ω(log k), e.g., 2^Ω(√{log k}) under suitable conditions.

Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.

We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m,n,t) (resp. s_N(m,n,t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2,t ≥ ⌊log n⌋+1 . In this work, we improve this bound when the probes are allowed to be superlinear in n, i.e., when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m,n,t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m,n,3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i.e., s_N(m,2,3) ≥ Ω(√m).

We prove a new upper bound on the size of codes C ⊆ {1, 2, 3, 4}nwith the property that every four distinct codewords in C have a coordinate where they all differ. Specifically, we provide a self-contained proof that such codes have size at most 26n/19+o(n), that is, rate bounded asymptotically 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 Komlós, 1984) and (Körner and Marton, 1988). Finally, using a combination of our approach with a simple idea which exploits powerful bounds on the minimum distance of codes in the Hamming space, we further improve the upper bound to 0.31477.

We construct a family of planar graphs {Gn}n≥4, where G_n has n vertices including a source vertex s, a sink vertex t, and edge weights that change linearly with a parameter λ such that, as λ varies in (-∞,+∞), the piece-wise linear cost of the shortest path from s to t has nΩ(logn)pieces. This shows that lower bounds obtained by Carstensen (1983) and Mulmuley & Shah (2001) for general graphs also hold for planar graphs, refuting a conjecture of Nikolova (2009). Gusfield (1980) and Dean (2009) showed that the number of pieces for every n-vertex graph with linear edge weights is nlogn+O(1). We generalize this result in two ways. (i) If the edge weights vary as a polynomial of degree at most d, then the number of pieces is n(logn+(α(n)+O(1))d) , where α(n) is the inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for R3, is n((logn)2+O(logn)).

We consider the problem of determining the zero-error list-decoding capacity of the q/(q-1) channel studied by Elias (1988). The q/(q-1) channel has input and output alphabet consisting of q symbols, say, X={x1, x2, ..., xq}; when the channel receives an input x ∈ X, it outputs a symbol other than x itself. Let n(m, q, ℓ) be the smallest n for which there is a code C ⊆ Xnof m elements such that for every list w1, w2,..., wℓ+1of distinct code-words from C, there is a coordinate j ∈ [n] that satisfies {w1[j], w2[j],..., wℓ+1[j]}=X. We show that for all constants α ≥ 1, we have n(m, q, αq)=exp(Ω(q)) log m. The lower bound obtained by Fredman and Komlós (1984) for perfect hashing implies that n(m, q, q-1)=exp(Ω(q)) log m; similarly, the lower bound obtained by Körner (1986) for nearly-perfect hashing implies that n(m, q, q)=exp(Ω(q)) log m. These results show that the zero-error list-decoding capacity of the q/(q-1) channel with lists of size at most q is exponentially small. Extending these bounds, Chakraborty et al. (2006) showed that the capacity remains exponentially small even if the list size is allowed to be as large as 1.58q. Our result implies that the zero-error list-decoding capacity of the q/(q-1) with list size αq (for every constant α ≥ 1) channel is exponentially small in q.

Saks and Wigderson [in Proceedings of the $27$th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that $R_0(f) = \Omega(D(f)^{0.753\ldots})$ for all Boolean functions $f$, where $R_0$ denotes the randomized zero-error query complexity and $D$ denotes the deterministic query complexity. We show that for the pointer function $\mathsf{GPW}^{r \times s}$ defined by Göös, Pitassi, and Watson [in Proceedings of the $56$th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) $R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})$ and (b) $R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})$, thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.

We consider the problem of finding small distance-preserving subgraphs of undirected, unweighted interval graphs that have k terminal vertices. We show that every interval graph admits a distance-preserving subgraph with O(k log k) branching vertices. We also prove a matching lower bound by exhibiting an interval graph based on bit-reversal permutation matrices. In addition, we show that interval graphs admit subgraphs with O(k) branching vertices that approximate distances up to an additive term of +1.

We prove a new, improved upper bound on the size of codes C ⊆{1, 2, 3, 4}nwith 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}.

We consider the non-adaptive 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 non-adaptively probing the bit vector at t places. Let s_N(m,n,t) be the minimum number of bits of storage needed for such a scheme. In this work, we show existence of non-adaptive and adaptive schemes for a range of t that improves an upper bound of Buhrman, Miltersen, Radhakrishnan and Srinivasan (2002) on s_N(m,n,t). For three non-adaptive probes, we improve the previous best lower bound on s_N(m,n,3) by Alon and Feige (2009).

Suppose 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.

The pointer function of G{ö}{ö}s, Pitassi and Watson \cite{DBLP:journals/eccc/GoosP015a} and its variants have recently been used to prove separation results among various measures of complexity such as deterministic, randomized and quantum query complexities, exact and approximate polynomial degrees, etc. In particular, the widest possible (quadratic) separations between deterministic and zero-error randomized query complexity, as well as between bounded-error and zero-error randomized query complexity, have been obtained by considering {\em variants}~\cite{DBLP:journals/corr/AmbainisBBL15} of this pointer function. However, as was pointed out in \cite{DBLP:journals/corr/AmbainisBBL15}, the precise zero-error complexity of the original pointer function was not known. We show a lower bound of $\widetildeΩ(n^{3/4})$ on the zero-error randomized query complexity of the pointer function on $Θ(n \log n)$ bits; since an $\widetilde{O}(n^{3/4})$ upper bound is already known \cite{DBLP:conf/fsttcs/MukhopadhyayS15}, our lower bound is optimal up to a factor of $\polylog\, n$.

Let f: {0,1}^n*{0,1}^n -> {0,1} be a 2-party function. For every product distribution mu on {0,1}^n*{0,1}^n, we show that CC^{mu}_{0.49}(f) = O(log(prt_{1/8}(f))*log(log(prt_{1/8}(f)))^2), where CC^{mu}_{epsilon}(f) is the distributional communication complexity of f with error at most epsilon under the distribution mu and prt_{1/8}(f) is the partition bound of f, as defined by Jain and Klauck [Proc. 25th CCC, 2010]. We also prove a similar bound in terms of IC_{1/8}(f), the information complexity of f, namely, CC^{mu}_{0.49}(f) = O((IC_{1/8}(f)*log(IC_{1/8}(f)))^2). The latter bound was recently and independently established by Kol [Proc. 48th STOC, 2016] using a different technique. We show a similar result for query complexity under product distributions. Let g: {0,1}^n -> {0,1} be a function. For every bit-wise product distribution mu on {0,1}^n, we show that QC^{mu}_{0.49}(g) = O((log(qprt_{1/8}(g))*log(log(qprt_{1/8}(g))))^2), where QC^{mu}_{epsilon}(g) is the distributional query complexity of f with error at most epsilon under the distribution mu and qprt_{1/8}(g) is the query partition bound of the function g. Partition bounds were introduced (in both communication complexity and query complexity models) to provide LP-based lower bounds for randomized communication complexity and randomized query complexity. Our results demonstrate that these lower bounds are polynomially tight for product distributions.

We initiate the study of a quantity that we call coordination complexity. In a distributed optimization problem, the information defining a problem instance is distributed among n parties, who need to each choose an action, which jointly will form a solution to the optimization problem. The coordination complexity represents the minimal amount of information that a centralized coordinator, who has full knowledge of the problem instance, needs to broadcast in order to coordinate the n parties to play a nearly optimal solution.

We consider the problem of communication over a classical-quantum broadcast channel with one sender and two receivers. Generalizing the classical inner bounds shown by Marton and the recent quantum asymptotic version shown by Savov and Wilde, we obtain one-shot inner bounds in the quantum setting. Our bounds are stated in terms of hypothesis testing and one-shot max divergences. These results give a full justification of the claims of Savov and Wilde in the classical-quantum asymptotic iid setting; the techniques also yield similar bounds in the information spectrum setting. We obtain these results using a different analysis of the random codebook argument; our method yields a classical one-shot Marton bound with a common message and a classical one-shot mutual covering lemma based on rejection sampling.

We 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. Several recent works investigate s(m,n,t) for various ranges of the parameter; we obtain improvements over some of the bounds shown by Buhrman, Miltersen, Radhakrishnan, and Srinivasan (2002) and Alon and Feige (2009).

We consider the communication cost of computing functions when inputs are distributed among the vertices of an undirected graph. The communication is assumed to be point-to-point: a processor sends messages only to its neighbors. The processors in the graph act according to a pre-determined protocol, which can be randomized and may err with some small probability. The communication cost of the protocol is the total number of bits exchanged in the worst case. Extending recent work that assumed that the graph was the complete graph (with unit edge lengths), we develop a methodology for showing lower bounds that are sensitive to the graph topology. In particular, for a broad class of graphs, we obtain a lower bound of the form Ω(k2n), for computing a function of k inputs, each of which is n-bits long and located at a different vertex. Previous works obtained lower bounds of the form Ω(k n). This methodology yields a variety of other results including the following: A tight lower bound (ignoring poly-log factors) for Element Distinctness, settling a question of Phillips, Verbin and Zhang (SODA '12), a distributed XOR lemma, a lower bound for composed functions, settling a question of Phillips et al., new topology-dependent bounds for several natural graph problems considered by Woodruff and Zhang (DISC '13). To obtain these results we use tools from the theory of metric embeddings and represent the topological constraints imposed by the graph as a collection of cuts, each cut providing a setting where our understanding of two-party communication complexity can be effectively deployed.

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph G and a root node r, we seek a single spanning tree T of minimum stretch, where the stretch of T is defined to be the maximum ratio, over all terminal sets X, of the cost of the minimal sub-tree TXof T that connects X to r to the cost of an optimal Steiner tree connecting X to r in G. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. graphs with 2O(√log n)-stretch. We also give a polynomial time We provide a polynomial time UST construction for general polylog(n)-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch (o(nε) for any ε >; 0) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.

In online set packing (OSP), elements arrive online, announcing which sets they belong to, and the algorithm needs to assign each element, upon arrival, to one of its sets. The goal is to maximize the number of sets that are assigned all their elements: a set that misses even a single element is deemed worthless. This is a natural online optimization problem that abstracts allocation of scarce compound resources, e.g., multipacket data frames in communication networks. We present a randomized competitive online algorithm for the weighted case with general capacity (namely, where sets may have different values, and elements arrive with different multiplicities). We prove a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximum set size and the maximum number of sets an element belongs to. We also present refined bounds that depend on the uniformity of these parameters.

We show that some topologies arising naturally in the context of wireless networking are low-degree, expander graphs.

We consider a scenario where large data frames are broken into a few packets and transmitted over the network. Our focus is on a bottleneck router: the model assumes that in each time step, a set of packets (a burst) arrives, from which only one packet can be served, and all other packets are lost. A data frame is considered useful only if none of its constituent packets is lost, and otherwise it is worthless. We abstract the problem as a new type of online set packing, present a randomized distributed algorithm and a matching lower bound on the competitive ratio for any randomized online algorithm. Our bounds are expressed in terms of the maximal burst size and the maximal number of packets per frame. We also present refined bounds that depend on the uniformity of these parameters.

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson-Guraswami-Sudan bounds. In particular, we show that for arbitrarily large fields FN, |FN| = N, for any ¿ ¿ (0,1), and K = N¿: (1) Existence: there exists a received word wN: FN¿ FNthat agrees with a super-polynomial number of distinct degree K polynomials on ¿ N¿¿points each; (2) Explicit: there exists a polynomial time constructible received word w'N: FN¿ FNthat agrees with a superpolynomial number of distinct degree K polynomials, on ¿2¿(log N)K points each. In both cases, our results improve upon the previous state of the art, which was ¿ N¿/¿ points of agreement for the existence case (proved by Justesen and Hoholdt), and ¿ 2N¿points of agreement for the explicit case (proved by Guruswami and Rudra). Furthermore, for ¿ close to 1 our bound approaches the Guruswami-Sudan bound (which is ¿(N K)) and implies limitations on extending their efficient Reed-Solomon list decoding algorithm to larger decoding radius. Our proof is based on some remarkable properties of sub-space polynomials. Using similar ideas, we then present a family of low rate codes that are efficiently list-decodable beyond the Johnson bound. This leads to an optimal list-decoding algorithm for the family of matrix-codes.

Given a data stream of length n over an alphabet [m] where n > m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O((log m)3) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace. We present various relaxations of the condition n > m, under which one can find duplicates efficiently.

We prove the following information-theoretic property about quantum states. Substate theorem: Let ρ and σ be quantum states in the same Hilbert space with relative entropy S (ρ ‖ σ) ≔ Tr ρ (log ρ - log σ) = c . Then for all ϵ > 0, there is a state ρ′ such that the trace distance ‖ρ′ - ρ‖ tr : Tr √(ρ′ - ρ) 2 ≤ ϵ, and ρ′/2 O ( c /ϵ 2 ) ≤ σ. It states that if the relative entropy of ρ and σ is small, then there is a state ρ′ close to ρ, i.e. with small trace distance ‖ρ′ - ρ‖ tr , that when scaled down by a factor 2 O ( c ) ‘sits inside’, or becomes a ‘substate’ of, σ. This result has several applications in quantum communication complexity and cryptography. Using the substate theorem, we derive a privacy trade-off for the set membership problem in the two-party quantum communication model. Here Alice is given a subset A ⊆ [ n ], Bob an input i ∈ [ n ], and they need to determine if i ∈ A . Privacy trade-off for set membership: In any two-party quantum communication protocol for the set membership problem, if Bob reveals only k bits of information about his input, then Alice must reveal at least n /2 O( k ) bits of information about her input. We also discuss relationships between various information theoretic quantities that arise naturally in the context of the substate theorem.

We show a tight lower bound of Omega(N\log\log N) on the number of transmissions required to compute several functions (including the parity function and the majority function) in a network of N randomly placed sensors, communicating using local transmissions, and operating with power near the connectivity threshold. This result considerably simplifies and strengthens an earlier result of Dutta, Kanoria Manjunath and Radhakrishnan (SODA 08) that such networks cannot compute the parity function reliably with significantly fewer than N\log \log N transmissions, thereby showing that the protocol with O(N\log \log N) transmissions due to Ying, Srikant and Dullerud (WiOpt 06) is optimal. We also observe that all the lower bounds shown by Evans and Pippenger (SIAM J. on Computing, 1999) on the average noisy decision tree complexity for several functions can be derived using our technique simply and in a unified way.

We show that massive attacks against sensor networks that use random key pre-distribution schemes cannot be cheap, provided that the parameters are set in the right way. By choosing them appropriately, any adversary whose aim is to compromise a large fraction of the communication links is forced, with overwhelming probability, to capture a large fraction of the nodes. This holds regardless of the information available to the adversary to select the nodes. We consider two important security properties: We say that the network is unassailable if the adversary cannot compromise a linear fraction of the communication links by compromising a sub-linear fraction of the nodes, and that the network is unsplittable if the adversary cannot partition the network into two (or more) linear size fragments. We show how to set the relevant parameters of random key pre-distribution---pool and key ring size---in such a way that the network is not only connected, but also provably unassailable and unsplittable with high probability. Moreover, we also show how to set the parameters in such a way to form a giant component in the network, a connected subgraph including, say, 99% of the sensors. Giant components emerge by using much smaller key rings, are sparse, and, quite remarkably, are provably unassailable and unsplittable as well. All these results are supported by experiments.

We give, for the first time, a precise mathematical analysis of the connectivity and security properties of sensor networks that make use of the random predistribution of keys. We also show how to set the parameters---pool and key ring size---in such a way that the network is not only connected with high probability via secure links but also provably resilient, in the following sense: We formally show that any adversary that captures sensors at random with the aim of compromising a constant fraction of the secure links must capture at least a constant fraction of the nodes of the network. In the context of wireless sensor networks where random predistribution of keys is employed, we are the first to provide a mathematically precise proof, with a clear indication of parameter choice, that two crucial properties---connectivity via secure links and resilience against malicious attacks---can be obtained simultaneously. We also show in a mathematically rigorous way that the network enjoys another strong security property. The adversary cannot partition the network into two linear size components, compromising all the links between them, unless it captures linearly many nodes. This implies that the network is also fault tolerant with respect to node failures. Our theoretical results are complemented by extensive simulations that reinforce our main conclusions.

LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(C(E)+1) +O(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719. 2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other.

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds in the works of S.M. Johnson (1962, 1963) and V. Guruswami and M. Sudan (1999). In particular, we show that for arbitrarily large fields FN, |FN| - N, for any delta isin (0,1), and K = Ndelta;: middot Existence: there exists a received word wN: FNrarr FNthat agrees with a super-polynomial number of distinct degree K polynomials on ap Nradicdeltapoints each; middot Explicit: there exists a polynomial time constructible received word w'N: FNrarr FNthat agrees with a super-polynomial number of distinct degree K polynomials, on ap 2radic(log N)K points each. In both cases, our results improve upon the previous state of the art, which was ap Ndelta/delta for the existence case in the work J. Justesen and T. Hoboldt (2001), and ap 2Ndeltafor the explicit one in the work of V. Guruswami and M. Sudan (2005). Furthermore, for delta close to 1 our bound approaches the Guruswami-Sudan bound (which is radicNK) and implies limitations on extending their efficient RS list decoding algorithm to larger decoding radius. Our proof method is surprisingly simple. We work with polynomials that vanish on subspaces of an extension field viewed as a vector space over the base field. These sub-space polynomials are a subclass of linearized polynomials that were first studied by O. Ore (1933, 1934) in the 1930s, and later by coding theorists. For us their main attraction is their sparsity and abundance of roots, virtues that recently won them pivotal roles in probabilistically checkable proofs of proximity in the works of E. Ben-Sasson et al. (2004) and E. Ben-Sasson and M. Sudan (2005) and sub-linear proof verification in the work of E. Ben-Sasson et al. (2005)

Consider a two-party quantum communication protocol for computing some function f : {0, 1}/sup n/ /spl times/ {0, 1}/sup n/ /spl rarr/ Z. We show that the first message of P can be compressed to 0(k) classical bits using prior entanglement if it carries at most k bits of information about the sender's input. This implies a general direct sum result for one-round and simultaneous quantum protocols. It also implies a new round elimination lemma in quantum communication, which allows us to extend recent classical lower bounds on the cell probe complexity of some data structure problems, e.g. approximate nearest neighbor searching on the Hamming cube {0, 1}/sup n/, to the quantum setting. We then show an optimal tradeoff between the privacy losses of Alice and Bob in computing f in terms of the one-round quantum communication complexity of f with prior entanglement. This tradeoff is independent of the number of rounds of communication. The above message compression and privacy tradeoff results use a lot of qubits of prior entanglement, leading one to wonder how much prior entanglement is really required by a quantum protocol. We show that Newman's [1991] technique of reducing the number of public coins in a classical protocol cannot be lifted to the quantum setting. We do this by defining a general notion of black-box reduction of prior entanglement that subsumes Newman's technique. Intuitively, a black-box reduction does not change the unitary transforms of Alice and Bob; it only decreases the amount of entanglement of the prior entangled state. We prove that such a black-box reduction is impossible for quantum protocols by exhibiting a particular one-round quantum protocol for the equality function where the black-box technique fails to reduce the amount of prior entanglement by more than a constant factor.

We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).

We 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)).

We show that some topologies arising naturally in the context of wireless networking are low-degree, expander graphs.

We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input X/sub i/ /spl sube/ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X/sub 1/,...,X/sub t/). We consider the class of Boolean valued functions whose value depends only on X/sub 1/ /spl cap/.../spl cap/ X/sub t/; that is, for each F in this class there is an f/sub F/ : 2/sup [n]/ /spl rarr/ {0,1}, such that F(X/sub 1/,...,X/sub t/) = f/sub F/(X/sub 1/ /spl cap/.../spl cap/ X/sub t/). We show that the t-party k-round communication complexity of F is /spl Omega/(s/sub m/(f/sub F/)/(k/sup 2/)), where s/sub m/(f/sub F/) stands for the monotone sensitivity of f/sub F/' and is defined by s/sub m/(f/sub F/) = /sup /spl utri// max/sub S/spl sube//[n] |{i : f/sub F/(S /spl cup/ {i}) /spl ne/ f/sub F/(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange /spl Omega/(n/k/sup 2/) qubits. An upper bound of O(n/k) can be derived from the O(/spl radic/n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the /spl Omega/(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 /spl les/ k /spl Lt/ n/sup 1/4 /, improves the lower bound of /spl Omega/(/spl radic/n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange /spl Omega/(n/sup 1/3/) qubits. This, however, falls short of the optimal /spl Omega/ (/spl radic/n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L/sub /spl infin// function considered in Z. Bar-Yossef et al. (2002).

An error-correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding of the message. Katz and Trevisan (2000) showed that any such code C: {0, 1} /spl rarr/ /spl Sigma//sup m/ with a decoding algorithm that makes at most q probes must satisfy m = /spl Omega/((n/log |/spl Sigma/|)/sup q/(q-1)/). They assumed that the decoding algorithm is non-adaptive, and left open the question of proving similar bounds for adaptive decoders. We improve the results of Katz and Trevisan (2000) in two ways. First, we give a more direct proof of their result. Second, and this is our main result, we prove that m = /spl Omega/((n/log|/spl Sigma/|)/sup q/(q-1)/) even if the decoding algorithm is adaptive. An important ingredient of our proof is a randomized method for smoothing an adaptive decoding algorithm. The main technical tool we employ is the Second Moment Method.

We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(/spl rho//spl par//spl sigma/)/spl Delta/=Tr /spl rho/(log /spl rho/-log /spl sigma/), of two quantum states /spl rho/ and /spl sigma/ is at most c, then /spl rho//2/sup O(c)/ 'sits inside' /spl sigma/. Using this 'substate' theorem, we give tight lower bounds for the privacy loss of bounded error quantum communication protocols for the index function problem. We also use the 'substate' theorem to give tight lower bounds for the k-round bounded error quantum communication complexity of the pointer chasing problem, when the wrong player starts, and all the log n bits of the kth pointer are desired.

We study the it static membership problem: Given a set S of at most n keys drawn from a universe U of size m, store it so that queries of the form "Is u in S?" can be answered by making few accesses to the memory. We study schemes for this problem that use space close to the information theoretic lower bound of $\Omega(n\log(\frac{m}{n}))$ bits and yet answer queries by reading a small number of bits of the memory. We show that, for $\epsilon > 0$, there is a scheme that stores $O(\frac{n}{\epsilon^2}\log m)$ bits and answers membership queries using a randomized algorithm that reads just one bit of memory and errs with probability at most $\epsilon$. We consider schemes that make no error for queries in S but are allowed to err with probability at most $\epsilon$ for queries not in S. We show that there exist such schemes that store $O((\frac{n}{\epsilon})^2 \log m)$ bits and answer queries using just one bitprobe. If multiple probes are allowed, then the number of bits stored can be reduced to $O(n^{1+\delta}\log m)$ for any $\delta > 0$. The schemes mentioned above are based on probabilistic constructions of set systems with small intersections. We show lower bounds that come close to our upper bounds (for a large range of n and $\epsilon$): Schemes that answer queries with just one bitprobe and error probability $\epsilon$ must use $\Omega(\frac{n}{\epsilon\log(1/\epsilon)} \log m)$ bits of storage; if the error is restricted to queries not in S, then the scheme must use $\Omega(\frac{n^2}{\epsilon^2 \log (n/\epsilon)}\log m)$ bits of storage. We also consider deterministic schemes for the static membership problem and show tradeoffs between space and the number of probes.

Studies the quantum complexity of the static set membership problem: given a subset S (|S|/spl les/n) of a universe of size m(/spl Gt/n), store it as a table, T:(0,1)/sup r//spl rarr/(0,1), of bits so that queries of the form 'is x in S?' can be answered. The goal is to use a small table and yet answer queries using a few bit probes. This problem was considered by H. Buhrman et al. (2000), who showed lower and upper bounds for this problem in the classical deterministic and randomised models. In this paper, we formulate this problem in the "quantum bit-probe model". We assume that access to the table T is provided by means of a black-box (oracle) unitary transform O/sub T/ that takes the basis state (y,b) to the basis state |y,b/spl oplus/T(y)>. The query algorithm is allowed to apply O/sub T/ on any superposition of basis states. We show tradeoff results between the space (defined as 2/sup r/) and the number of probes (oracle calls) in this model. Our results show that the lower bounds shown by Buhrman et al. for the classical model also hold (with minor differences) in the quantum bit-probe model. These bounds almost match the classical upper bounds. Our lower bounds are proved using linear algebraic arguments.

We study the static membership problem: Given a set S of at most n keys drawn from a universe of size m, store it so that queries of the form "Is x in S?" can be answered quickly.We study schemes for this problem that use space close to the information theoretic lower bound of 12(nlog(~)) bits and yet answer queries by reading a small number of bits of the memory.We show that there is a randomized scheme with error e that stores O(;~-logm) bits and answers queries using a single bitprobe.It is based on a family of sets with small intersections.If the error is required to be restricted to queries not in S, then we have a scheme that stores o((n) 2 logm) bits, answers queries with one bitprobe and works with probability of error less than e.We also show that better schemes with one-sided error can be obtained if more probes are allowed.We show lower bounds that come close to our upper bounds (for a large range of n and e): Schemes that answer queries with just one bitprobe and error probability e must use f~(~ log m) bits of storage; if the error is restricted to r~ 2 queries not in S, then the scheme must use ~(~ log m) bits of storage.We also consider deterministic schemes for the static membership problem and show upper and lower bounds.Ijaikumar, venkat}@tcs.tifr.

We show that the size of the smallest depth-two N-superconcentrator is $$ \Theta(N\log^2 N/\log\log N). $$ Before this work, optimal bounds were known for all depths except two. For the upper bound, we build superconcentrators by putting together a small number of disperser graphs; these disperser graphs are obtained using a probabilistic argument. For obtaining lower bounds, we present two different methods. First, we show that superconcentrators contain several disjoint disperser graphs. When combined with the lower bound for disperser graphs of Kovari, Sós, and Turán, this gives an almost optimal lower bound of $\Omega( N (\log N/\log \log N)^2)$ on the size of N-superconcentrators. The second method, based on the work of Hansel, gives the optimal lower bound. The method of Kovari, Sós, and Turán can be extended to give tight lower bounds for extractors, in terms of both the number of truly random bits needed to extract one additional bit and the unavoidable entropy loss in the system. If the input is an n-bit source with min-entropy k and the output is required to be within a distance of $\epsilon$ from uniform distribution, then to extract even one additional bit, one must invest at least $\log(n-k) + 2\log(1/\epsilon) - O(1)$ truly random bits; to obtain m output bits one must invest at least $m-k+2\log(1/\epsilon)-O(1)$. Thus, there is a loss of $2\log(1/\epsilon)$ bits during the extraction. Interestingly, in the case of dispersers this loss in entropy is only about $\log\log (1/\epsilon)$.

The following pointer chasing problem plays a central role in the study of bounded round communication complexity. There are two players A and B. There are two sets of vertices V/sub A/ and V/sub B/ of size n each. Player A is given a function f/sub A/: VA/spl rarr/VB and player B is given a function f/sub B/: VB/spl rarr/VA. In the problem g/sub k/ the players have to determine the vertex reached by applying f/sub A/ and f/sub B/ alternately, k times starting with a fixed vertex v/sub 0//spl isin/V/sub A/. That is, in g/sub 1/, they must determine f/sub A/(v/sub 0/), in g/sub 2/ they must determine f/sub B/(f/sub A/(v/sub 0/)), in g/sub 3/ they must determine f/sub A/(f/sub B/(f/sub A/(v/sub 0/))), and so on.

We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. Damm, Jukna and Sgall [2] showed an upper bound of O(n log(k\\Gamma 1) n) for this problem. We prove a matching lower bound; this improves the lower bound of \\Omega (n) shown by Nisan and Wigderson [11], and yields a corresponding improvement in the hierarchy results derived in [11, 7] 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 Klauck [7]) 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.

We show that for all large n, every n-uniform hypergraph with at most 0.7/spl radic/(n/lnn)/spl times/2/sup n/ edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC/sup 1/ versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n/sup 1/3-0(1)//spl times/2/sup n/ due to Beck (1978). We further generalize this to a "local" version, improving on one of the first applications of the Lovasz Local Lemma.

We show that the minimum size of a depth-two N-superconcentrator is /spl Theta/(Nlog/sup 2/N/loglogN). Before this work, optimal bounds were known for all depths except two. For the upper bound, we build superconcentrators by putting together a small number of disperser graphs; these disperser graphs are obtained using a probabilistic argument. We present two different methods for showing lower bounds. First, we show that superconcentrators contain several disjoint disperser graphs. When combined with the lower bound for disperser graphs due to Kovari, Sos and Turan, this gives an almost optimal lower bound of /spl Omega/(N(log N/loglog N)/sup 2/) on the size of N-superconcentrators. The second method, based on the work of Hansel (1964), gives the optimal lower bound. The method of the Kovari, Sos and Turan can be extended to give tight lower bounds for extractors, both in terms of the number of truly random bits needed to extract one additional bit and in terms of the unavoidable entropy loss in the system. If the input is an n-bit source with min-entropy /spl kappa/ and the output is required to be within a distance of E from uniform distribution, then to extract even a constant number of additional bits, one must invest at least log(n-/spl kappa/)+2 log(1//spl epsiv/)-O(1) truly random bits; to obtain m output bits one must invest at least m-/spl kappa/+2 log(1//spl epsiv/)-O(1). Thus, there is a loss of 2 log(1//spl epsiv/) bits during the extraction. Interestingly in the case of dispersers this loss in entropy is only about loglog(1//spl epsiv/).

We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S 1−ɛ(d) ) (where ɛ(d) = 4 −d) of its input values. This implies a superlinear size lower bound for a large class of functions. Using this, we obtain a function computable by a uniform family of constant depth polynomial size circuits that cannot be computed by constant depth circuits of linear size. We give circuit constructions that show that the bound O(S 1−ɛ(d) ) is near optimal. We also study the complexity of computing threshold functions. The function T n r has the value 1 iff at least r of its inputs have the value 1. We show that a circuit computing T n r has at least Ω(r 2 (log n) / log r) gates, for r ≤ n 1/3, improving previous bounds. We also show a trade-off between the number of gates and the number of wires in a threshold circuit, namely, a circuit with G (< n/2) gates and W wires computing T n r satisfies W ≥ Ω(nr(log n)/(log(G / log n))), showing that it is not possible to simultaneously optimize the number of gates and wires in a threshold circuit. Our bounds for threshold functions are based on a combinatorial lemma of independent interest. 1

Theminimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ+2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turan’s bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved\((2\bar d + 3)/5\) performance ratio on graphs with average degree\(\bar d\), improving on the previous best\((\bar d + 1)/2\) of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy.

We consider the problem of computing threshold functions using directed and undirected monotone contact networks. Our main results are the following. First, we show that there exist directed monotone contact networks that compute T/sub k//sup n/, 2/spl les/k/spl les/n-1, of size O(k(n-k+2)log(n-k+2)). This bound is almost optimal for small thresholds, since there exists an /spl Omega/(knlog (n/(k-1))) lower bound. Our networks are described explicitly; the previously best upper bound known, obtained from the undirected networks of Dubiner and Zwick, used non-constructive arguments and gave directed networks of size O(k/sup 3.99/nlog n). Second, we show a lower bound of O(nlogloglog n) on the size of undirected monotone contact networks computing T/sub n-1//sup n/, improving the 2(n-1) lower bound of Markov. Combined with our upper bound result, this shows that directed monotone contact networks compute some threshold functions more easily than undirected networks.>

The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.>

The computation of threshold functions using formulas over the basis (AND, OR, NOT) is considered. It is shown that every monotone formula that computes the threshold function T/sub k//sup n/2>