The first linear programming bound is the best known asymptotic upper bound for binary codes, for a certain subrange of distances. Starting from the work of Friedman and Tillich (2005), there are, by now, some arguably easier and more direct arguments for this bound. We show that this more recent line of argument runs into certain difficulties if one tries to go beyond this bound [say, towards the second linear programming bound of McEliece et al. (1977)]. Stated more constructively, we show that certain necessary requirements have to be met in order to produce a feasible solution to the dual linear program of Delsarte (1973), which improves on the first linear programming bound, following this line of argument.

We consider the problem of discrimination between two pure quantum states. It is well known that the optimal measurement under both the error-probability and log-loss criteria is a projection, while under an “erasure-distortion” criterion it is a three-outcome positive operator-valued measure (POVM). These results were derived separately. We present a unified approach which finds the optimal measurement under any distortion measure that satisfies a convexity relation with respect to the Bhattacharyya distance. Namely, whenever the measure is relatively convex (resp. concave), the measurement is the projection (resp. three-outcome POVM) above. The three above-mentioned results are obtained as special cases of this simple derivation. As for further measures for which our result applies, we prove that Rényi entropies of order 1 and above (resp. 1/2 and below) are relatively convex (resp. concave). A special setting of great practical interest, is the discrimination between two coherent-light waveforms. In a remarkable work by Dolinar it was shown that a simple detector consisting of a photon counter and a feedback-controlled local oscillator obtains the quantum-optimal error probability. Later it was shown that the same detector (with the same local signal) is also optimal in the log-loss sense. By applying a similar convexity approach, we obtain in a unified manner the optimal signal for a variety of criteria.

We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that: 1. BA protocols resilient against n/3 [resp., n/4] corruptions terminate (under attack) at the end of the first round with probability at most o(1) [resp., $$1/2+ o(1)$$ ]. 2. BA protocols resilient against a fraction of corruptions greater than 1/4 terminate at the end of the second round with probability at most $$1-\Theta (1)$$ . 3. For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against a fraction of corruptions greater than 1/3 [resp., 1/4] terminate at the end of the second round with probability at most o(1) [resp., $$1/2 + o(1)$$ ]. The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI). The third bound essentially matches the recent protocol of Micali (ITCS’17) that tolerates up to n/3 corruptions and terminates at the end of the third round with constant probability.

We strengthen the results from a recent work by the second author, achieving bounds on the weight distribution of binary linear codes that are successful under block-MAP (as well as bit-MAP) decoding on the BEC. We conclude that a linear code that is successful on the BEC can also decode over a range of binary memoryless symmetric (BMS) channels. In particular, applying the result of Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke from STOC 2016, we prove that a Reed–Muller code of positive rate R decodes errors on the p with high probability if p < 1/2 − √2−R(1−2−R).

Let p ≥ 2. We improve the bound ||f||p/ ||f||2≤ (p-1)s/2for a polynomial f of degree s on the boolean cube {0,1}n, which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of p and s, which is smaller than (p-1)s/2for any p > 2 and s > 0. We show the new bound to be tight, within a smaller order factor, for the Krawchouk polynomial of degree s. This implies several nearly-extremal properties of Krawchouk polynomials and Hamming spheres (equivalently, Hamming balls). In particular, Krawchouk polynomials have (almost) the heaviest tails among all polynomials of the same degree andl2norm.1The Hamming spheres have the following approximate edge-isoperimetric property: For all 1 ≤ s ≤ n/2, and for all even distances 0 ≤ i ≤ 2s(n-s) / n, the Hamming sphere of radius s contains, up to a multiplicative factor of O(i), as many pairs of points at distance i as possible, among sets of the same size (there is a similar, but slightly weaker and somewhat more complicated claim for all distances). This also implies that Hamming spheres are (almost) stablest with respect to noise among sets of the same size. In coding theory terms this means that a Hamming sphere (equivalently a Hamming ball) has the maximal probability of undetected error, among all binary codes of the same rate. We also describe a family of hypercontractive inequalities for functions on {0,1}n, which improve on the `usual' “ q → 2” inequality by taking into account the concentration of a function (expressed as the ratio between itslrnorms), and which are nearly tight for characteristic functions of Hamming spheres.1This has to be interpreted with some care.

Let T∈, 0 ≤ ∈ ≤ 1/2, be the noise operator acting on functions on the boolean cube {0, 1}n. Let f be a nonnegative function on {0, 1}nand let q ≥ 1. We upper bound the ℓqnorm of T∈f by the average ℓqnorm of conditional expectations of f, given sets of roughly (1 - 2∈)r(q)· n variables, where r is an explicitly defined function of q. We describe some applications for error-correcting codes and for matroids. In particular, we derive an upper bound on the weight distribution of BEC-capacity achieving binary linear codes and their duals. This improves the known bounds on the linear-weight components of the weight distribution of constant rate binary Reed-Muller codes for all (constant) rates.

Let 0n. Let f be a nonnegative function on {0,1}n. We upper bound the entropy of Tϵ f by the average entropy of conditional expectations of f, given sets of roughly (1-2ϵ)2n variables. In information-theoretic terms, we prove the following strengthening of Mrs. Gerber's Lemma: let X be a random binary vector of length n, and let Z be a noise vector, corresponding to a binary symmetric channel with crossover probability ϵ. Then, setting v = (1-2ϵ)2· n, we have (up to lower order terms): H(X⊕Z) ≥ n · H2(ϵ+ (1-2ϵ) · H2-1E|B| = vH ({Xi}iϵB}/v))). Assuming ϵ ≥ 1/2 - δ, for some absolute constant δ > 0, this inequality, combined with a strong version of a theorem of Friedgut et al., due to Jendrej et al., shows that if a Boolean function f is close to a characteristic function g of a subcube of dimension n-1, then the entropy of Tϵf is at most that of Tϵg. Taken together with a recent result of Ordentlich et al., this shows that the most informative Boolean function conjecture of Courtade and Kumar holds for high noise ϵ ≥1/2 - δ. Namely, if X is uniformly distributed in {0,1}nand Y is obtained by flipping each coordinate of X independently with probability ϵ, then, provided ϵ ≥ 1/2 - δ, for any Boolean function f holds I (f(X);Y) ≤ 1 - H(ϵ).

A square matrix V is called rigid if every matrix V' obtained by altering a small number of entries of $V$ has sufficiently high rank. While random matrices are rigid with high probability, no explicit constructions of rigid matrices are known to date. Obtaining such explicit matrices would have major implications in computational complexity theory. One approach to establishing rigidity of a matrix V is to come up with a property that is satisfied by any collection of vectors arising from a low-dimensional space, but is not satisfied by the rows of V even after alterations. In this paper we propose such a candidate property that has the potential of establishing rigidity of combinatorial design matrices over the field F_2. Stated informally, we conjecture that under a suitable embedding of F_2^n into R^n, vectors arising from a low dimensional F_2-linear space always have somewhat small Kolmogorov width, i.e., admit a non-trivial simultaneous approximation by a low dimensional Euclidean space. This implies rigidity of combinatorial designs, as their rows do not admit such an approximation even after alterations. Our main technical contribution is a collection of results establishing weaker forms and special cases of the conjecture above.

Our main technical result is that, in the coset leader graph of a linear binary code of block length n, the metric balls spanned by constant-weight vectors grow exponentially slower than those in (0, 11n. Following the approach of Friedman and Tillich, we use this fact to improve on the first linear programming bound on the rate of low-density parity check (LDPC) codes, as the function of their minimal relative distance. This improvement, combined with the techniques of Ben-Haim and Litsyn, improves the rate versus distance bounds for LDPC codes in a significant subrange of relative distances.

We give new lower and upper bounds on the permanent of a doubly stochastic matrix. Combined with previous work, this improves on the deterministic approximation factor. We also give a combinatorial application of the lower bound, proving S. Friedland's "Asymptotic Lower Matching Conjecture"for the monomer-dimer problem.

Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower-bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here we derive an upper bound that proves the conjecture.

Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here, we derive an upper bound that proves the conjecture.

We study the zero-undetected-error capacity of the discrete memoryless channel whose directed channel graph is the cyclic triangle. We show that this capacity is upper-bounded by log 2 and approaches log 2 as the crossover probabilities tend to zero.

We give a new model of learning motivated by smoothed analysis (Spielman and Teng, 2001). In this model, we analyze two new algorithms, for PAC-learning DNFs and agnostically learning decision trees, from random examples drawn from a constant-bounded product distributions. These two problems had previously been solved using membership queries (Jackson, 1995; Gopalan et al, 2005). Our analysis demonstrates that the "heavy" Fourier coefficients of a DNF suffice to recover the DNF. We also show that a structural property of the Fourier spectrum of any boolean function over "typical" product distributions. In a second model, we consider a simple new distribution over the boolean hypercube, one which is symmetric but is not the uniform distribution, from which we can learn O(log n)-depth decision trees in polynomial time.

Voting trees provide an abstract model of decision-making among a group of individuals in terms of an iterative procedure for selecting a single vertex from a tournament. A family of voting trees is said to implement a given voting rule if for every tournament it chooses according to the rule. While partial results concerning implementable rules and necessary conditions for implementability have been obtained, a complete characterization of voting rules implementable by trees has proven surprisingly hard to find. A prominent rule that cannot be implemented by trees is the Copeland rule, which singles out vertices with maximum degree. In this paper, we suggest a new angle of attack and re-examine the implementability of the Copeland solution using paradigms and techniques at the core of theoretical computer science. We study the extent to which voting trees can approximate the maximum degree, and give upper and lower bounds on the worst-case ratio between the degree of the vertex chosen by a tree and the maximum degree, both for the deterministic model concerned with a single fixed tree, and for randomizations over arbitrary sets of trees. Our main positive result is a randomization over surjective trees of polynomial size that provides an approximation ratio of at least 1/2. The proof is based on a connection between a randomization over caterpillar trees and a rapidly mixing Markov chain.

We study the relation of query complexity and soundness in probabilistically checkable proofs (PCPs). We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes q queries, has almost perfect completeness, and has soundness error at most $2q/2^q+\varepsilon$ for arbitrarily small $\varepsilon>0$. For values of q of the form $2^t-1$, the soundness error is $(q+1)/2^q+\varepsilon$. Charikar, Makarychev, and Makarychev show that there is a constant $\beta$ such that every language that has a verifier of query complexity q and a ratio of soundness error to completeness smaller than $\beta q/2^q$ is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight. As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree $\Delta$ within a factor better than $\Delta/(\log\Delta)^\alpha$ is Unique-Games-Hard for a certain constant $\alpha>0$. Our main technical results are (i) a connection between the Gowers uniformity of a boolean function and the influence of its variables and (ii) the proof that “Gowers uniform” functions pass the “hypergraph linearity test” approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.

Let p be a fixed prime number and N be a large integer. The "Inverse Conjecture for the Gowers Norm" states that if the "d-th Gowers norm" of a function f:FNp to Fp is non-negligible, that is larger than a constant independent of N, then f has a non-trivial correlation with a degree d-1 polynomial. The conjecture is known to hold for d=2,3 and for any prime p. In this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. Essentially the same result, with different bounds for correlation, was independently obtained by Green and Tao. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime p, for d = p2.

We define tests of boolean functions which distinguish between linear (or quadratic) polynomials, and functions which are very far, in an appropriate sense, from these polynomials. The tests have optimal or nearly optimal trade-offs between soundness and the number of queries.

We return to the study of the relation of query complexity and soundness in probabilistically checkable proofs.We present a PCP verifier for languages that are Unique-Games-Hard and such that the verifier makes q queries, has almost perfect completeness, and has soundness error at most 2q/2q+ε, for arbitrarily small ε>0. For values of q of the form 2t-1, the soundness error is (q+1)/2q+ε.Charikar et al. show that there is a constant c such that for every language that has a verifier of query complexity q, and a ratio of soundness error to completeness smaller than cq/2q is decidable in polynomial time. Up to the value of the multiplicative constant and to the validity of the Unique Games Conjecture, our result is therefore tight.As a corollary, we show that approximating the Maximum Independent Set problem in graphs of degree Δ within a factor better than Δ/(log Δ)c is Unique-Games-Hard for a certain constant c>0.Our main technical results are (i) a connection between the Gowers uniformity of a Boolean function and the influence of its variables and (ii) the proof that "Gowers uniform" functions pass the "hypergraph linearity test" approximately with the same probability of a random function. The connection between Gowers uniformity and influence might have other applications.

We prove two results about the value of Delsarte 's linear program for binary codes. Our main result is a new lower bound on the value of the program, which, in particular, is nearly tight for low rate codes. We also give an easy proof of a (known) upper bound, which coincides with the best known bound for a wide range of parameters.

We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter /spl epsi/. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in /spl epsi//sup -1/. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms. We then provide a lower bound of /spl Omega//spl tilde/(/spl radic/ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of /spl Omega/(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z/sub 2//sup q/ that may be interesting in its own right. We show that for some t(q) = O/spl tilde/(q/sup 2/), the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk. We also discuss related questions. In particular, when given in advance a known k junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and /spl epsi/.

The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are 'far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube {1,…,m}n. These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2-CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest.

We consider the problem of determining whether a given function $f:{\{0,1\}}^n\to{\{0,1\}}$ belongs to a certain class of Boolean functions $\cal F$ or whether it is far from the class. More precisely, given query access to the function f and given a distance parameter $\epsilon$, we would like to decide whether $f \in \cal F$ or whether it differs from every $g\in \cal F$ on more than an $\epsilon$-fraction of the domain elements. The classes of functions we consider are singleton ("dictatorship") functions, monomials, and monotone disjunctive normal form functions with a bounded number of terms. In all cases we provide algorithms whose query complexity is independent of n (the number of function variables), and linear in $1/\epsilon$.

We present a deterministic polynomial algorithm that computes the mixed discriminant of an n-tuple of positive semidefinite matrices to within a multiplicative factor of e ~.To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n-tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling.We obtain tight upper and lower bounds on the mixed discriminant of doubly stochasic n-tuples, proving a conjecture of Bapat, and generalizing the van der Waerden -Falikman -Egorychev theorem.As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in 1~ ~ to within a multiplicative factor of n °(').This answers a question of Dyer, Gritzmann and Hufnagel.

Article A PCP characterization of NP with optimal amortized query complexity Share on Authors: Alex Samorodnitsky Institute for Advanced Study and DIMACS Institute for Advanced Study and DIMACSView Profile , Luca Trevisan Columbia University and DIMACS Columbia University and DIMACSView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 191–199https://doi.org/10.1145/335305.335329Online:01 May 2000Publication History 101citation487DownloadsMetricsTotal Citations101Total Downloads487Last 12 Months17Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present a deterministic strongly polynomial algorithm that computes the permanent of a nonnegativo n x m matrix to within a multiplicative factor of e".To thii end we develop the first strongly polynomial time algorithm for matrix scaling -an important nonlinear optimization problem with many applications.Our work suggests a (slow) decision algorithm for bipartite perfect matching, conceptually different from known approaches.