Search

The complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. The method is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe's method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly polynomial time to the minimum norm point problem over a simplex.

A CM-order is a reduced order equipped with an involution that mimics complex conjugation. The Witt-Picard group of such an order is a certain group of ideal classes that is closely related to the "minus part" of the class group. We present a deterministic polynomial-time algorithm for the following problem, which may be viewed as a special case of the principal ideal testing problem: given a CM-order, decide whether two given elements of its Witt - Picard group are equal. In order to prevent coefficient blow-up, the algorithm operates with lattices rather than with ideals. An important ingredient is a technique introduced by Gentry and Szydlo in a cryptographic context. Our application of it to lattices over CM-orders hinges upon a novel existence theorem for auxiliary ideals, which we deduce from a result of Konyagin and Pomerance in elementary number theory.

Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al. [Maximally recoverable codes for grid-like topologies, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 2092-2108] studied the alphabet size needed for such codes in grid topologies and gave a combinatorial characterization for it. Consider a labeling of the edges of the complete bipartite graph Kn, n, with labels coming from Fd2 that satisfies the following condition: for any simple cycle, the sum of the labels over its edges is nonzero. The minimal d where this is possible controls the alphabet size needed for maximally recoverable codes in n × n grid topologies. Prior to the current work, it was known that d is between (log n)2 and n log n. We improve both bounds and show that d is linear in n. The upper bound is a recursive construction which beats the random construction. The lower bound follows by first relating the problem to the independence number of the Birkhoff polytope graph, and then providing tight bounds for it using the representation theory of the symmetric group.

Suppose that you have n truly random bits x = (x1, . . ., xn) and you wish to use them to generate m n pseudorandom bits y = (y1, . . ., ym) using a local mapping, i.e., each yi should depend on at most d = O(1) bits of x. In the polynomial regime of m = ns, s > 1, the only known solution, originating from [Goldreich, Electronic Colloquium on Computational Complexity (ECCC), 2000], is based on random local functions: Compute yi by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct input indices (xi1 , . . ., xid). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results: (1) We show that pseudorandomness against F2-linear adversaries (i.e., the distribution y has small bias) is achieved if the predicate is (a) k = Ω(s)-resilient, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local small-biased generator can have output length of nΩ(d), answering an open question of Mossel, Shpilka, and Trevisan [Proceedings of FOCS, 2003]. Our negative result shows that a candidate for a pseudorandom generator proposed by Applebaum [Comput. Complexity, 25 (2016), pp. 667–722] and by O’Donnell and Witmer [Proceedings of CCC 2014] is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins, and Vempala [Proceedings of STOC 2015] regarding the hardness of planted constraint satisfaction problems. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the polynomial calculus proof system. We show that algebraic attacks succeed if and only if the predicate P has rational degree e = Θ(s), where the rational degree of a predicate P is the smallest integer e for which there exist degree e polynomials Q, R, not both zero, such that PQ = R. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by Applebaum [Comput. Complexity, 25 (2016), pp. 667–722].

Let f : {0, 1}n → {0, 1} be a boolean function. Its associated XOR function is the two-party function f(x, y) = f(x y). We show that, up to polynomial factors, the deterministic communication complexity of f is equal to the parity decision tree complexity of f. This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible, for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message or a completely unrelated value. Although such codes do not exist if the family of “tampering functions” F is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so-called split-state model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient non-malleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature but either (1) were constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as noninteractive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function L, R over the vector space Fpn (for a prime p and large enough dimension n): if L and R are uniformly random over Fpn, and f, g : Fpn → Fpn are two arbitrary functions on L and R, then the joint distribution (L, R, f(L), g(R)) is “close” to the convex combination of “affine distributions” ((U, aU + b) | a, b ∈ Fp), where U is uniformly random in Fp. In turn, the proof of this surprising property of the inner product function critically relies on some results from additive combinatorics, including the so-called quasi-polynomial Freiman–Ruzsa theorem, which was recently established by Sanders [Anal. PDE, 5 (2012), pp. 627–655] as a step toward resolving the polynomial Freiman–Ruzsa conjecture [B. Green, in Surveys in Combinatorics, London Mathematical Society, London, 2005, pp. 1–29].

We develop a new method to prove communication lower bounds for composed functions of the form fogn, where f is any boolean function on n inputs and g is a sufficiently "hard" two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of fogn can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only "query" a few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of fogn in all known one-sided (i.e., not closed under complement) zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work. We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠= SBPcc. These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118-134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043-1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701-712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.

We give a lower bound on the iteration complexity of a natural class of Lagrangianrelaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with m random 0/1-constraints on n variables, with high probability, any such algorithm requires Ω(ρ log(m)/∈2) iterations to compute a (1 + ∈)-approximate solution, where ρ is the width of the input. The bound is tight for a range of the parameters (m, n, ρ, ∈). The algorithms in the class include Dantzig-Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of (1 + ∈)-approximate mixed strategies for random two-player zero-sum 0/1-matrix games.

Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer [Trans. Amer. Math. Soc., 289 (1985), pp. 679-706]: In any system of n sets in a universe of size n, there always exists a coloring which achieves discrepancy 6 √ n. The original proof of Spencer was existential in nature and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal [Proceedings of FOCS, 2010, pp. 3-10] gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencer's result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is truly constructive in that it does not appeal to the existential arguments, giving a new proof of Spencer's theorem and the partial coloring lemma.

A matching vector (MV) family modulo m is a pair of ordered lists U = (u1,ut) and V = (v1,vt) where ui, vj ∈ ℤnm with the following inner product pattern: for any i, 〈ui, vi〉 = 0, and for any i ≠ j, 〈ui, vj〉 ≠ 0. An MV family is called q-restricted if inner products 〈ui, vj〉 take at most q different values. Our interest in MV families stems from their recent application in the construction of subexponential locally decodable codes (LDCs). There, q-restricted MV families are used to construct LDCs with q queries, and there is special interest in the regime where q is constant. When m is a prime it is known that such constructions yield codes with exponential block length. However, for composite m the behavior is dramatically different. A recent work by Efremenko [SIAM J. Comput., 40 (2011), pp. 1154-1178] (based on an approach initiated by Yekhanin [J. ACM, 55 (2008), pp. 1-16]) gives the first subexponential LDC with constant queries. It is based on a construction of an MV family of superpolynomial size by Grolmusz [Combinatorica, 20 (2000), pp. 71-86] modulo composite m. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When q is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus m is constant (as it is in the construction of Efremenko) we prove a superpolynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman.Ruzsa conjecture over ℤm.

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function f : np → Fp with polynomials of degree at most d ≤ p is nonnegligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analogue of proximity oblivious testing, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for nonlinear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erd̈os, Lov́asz, and Spencer to the context of additive number theory. © 2014 Society for Industrial and Applied Mathematics.

Minimum-weight triangulation (MWT) is NP-hard. It has a polynomial-time constant-factor approximation algorithm, and a variety of effective polynomial-time heuristics that, for many instances, can find the exact MWT. Linear programs (LPs) for MWT are well-studied, but previously no connection was known between any LP and any approximation algorithm or heuristic for MWT. Here we show the first such connections: For an LP formulation due to Dantzig, Hoffman, and Hu [Math. Programming, 31 (1985), pp. 1-14], (i) the integrality gap is constant, and (ii) given any instance, if the aforementioned heuristics find the MWT, then so does the LP. © 2014 Society for Industrial and Applied Mathematics.

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function f : np → Fp with polynomials of degree at most d ≤ p is nonnegligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analogue of proximity oblivious testing, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for nonlinear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erd̈os, Lov́asz, and Spencer to the context of additive number theory. © 2014 Society for Industrial and Applied Mathematics.

An approximate membership data structure is a randomized data structure representing a set which supports membership queries. It allows for a small false positive error rate but has no false negative errors. Such data structures were first introduced by Bloom in the 1970s and have since had numerous applications, mainly in distributed systems, database systems, and networks. The algorithm of Bloom (known as a Bloom filter) is quite effective: it can store an approximation of a set S of size n by using only ≈ 1.44n log2(1/ε) bits while having false positive error ε. This is within a constant factor of the information-theoretic lower bound of n log2(1/ε) for storing such sets. Closing this gap is an important open problem, as Bloom filters are widely used in situations where storage is at a premium. Bloom filters have another property: they are dynamic. That is, they support the iterative insertions of up to n elements. In fact, if one removes this requirement, there exist static data structures that receive the entire set at once and can almost achieve the information-theoretic lower bound; they require only (1 + o(1))n log2(1/ε) bits. Our main result is a new lower bound for the space requirements of any dynamic approximate membership data structure. We show that for any constant ε > 0, any such data structure that achieves false positive error rate of ε must use at least C(ε) · n log2(1/ε) memory bits, where C(ε) > 1 depends only on ε. This shows that the information-theoretic lower bound cannot be achieved by dynamic data structures for any constant error rate. © 2013 Society for Industrial and Applied Mathematics.

We give a polynomial-time approximation scheme for the generalization of Huffman coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1 +?)-approximate solution in time O(n+f(?) log3 n), where n is the input size. © 2012 Society for Industrial and Applied Mathematics.

A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over A ⊆ {1, 2,⋯, n}, the objective function |A| - Σ i ξ i 1 (i ∈ A, i + 1 ∈ A) for given ξi > 0. This problem, with random (ξi), provides a test example for studying the relationship between optimal and near-optimal solutions of combinatorial optimization problems. We show that, amongst solutions difiering from the optimal solution in a small proportion δ of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order δ 2 but not of smaller order. We conjecture this relationship holds widely in the context of dynamic prog amming over random data, and Monte Carlo simulations for the Kauffman-Levin NK model are consistent with the conjecture. This work is a technical contribution to a broad program initiated in [D. J. Aldous and A. G. Percus, Proc. Natl. Acad. Sci. USA, 100 (2003), pp. 11211-11215] of relating such scaling exponents to the algorithmic difficulty of optimization problems. © 2009 Society for Industrial and Applied Mathematics.

For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k]q, a simple counting argument shows that for any integer 0 < g < n, there exists at least one Hamming ball of radius n - g, which contains at least ( gn)/qg-k many codewords. Let ĝ(n, k, q) be the smallest positive integer g such that (gn)/q g-k ≤ 1. One knows that k - 1 ≤ ĝ(n, k, q) ≤ √n(k - 1) ≤ n. For the distance bound up to n - √n(k - 1), it is known that both the list and bounded distance decoding can be solved efficiently. For the distance bound between n - √n(k - 1) and n-ĝ(n, k, q), we do not know whether the Reed-Solomon code is list or bounded distance decodable; nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: (1) List decoding cannot be done for radius n - ĝ(n, k, q) or larger, unless the discrete logarithm over F qĝ(n, k, q)-k is easy. (2) Let h and g be positive integers satisfying q ≥ max(g2, (h - 1)2+ε) and g ≥ (4/ε + 2)(h +1) for a constant ε > 0. We show that the discrete logarithm problem over F qh can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g - h]q with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the list decoding problem of Reed-Solomon codes, although the infeasible radius that we obtain is much larger than the radius, which is known to be feasible, it is the first nontrivial bound. Our result on the bounded distance decodability of Reed-Solomon codes is also the first of its kind. The main tools for obtaining these results are an interesting connection between the problem of list decoding of Reed-Solomon code, the problem of a discrete logarithm over finite fields, and a generalization of Katz's theorem on representations of elements in an extension finite field by products of distinct linear factors. © 2007 Society for Industrial and Applied Mathematics.

For an error-correcting code and a distance bound, the list decoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the list decoding problem. For a Reed-Solomon code [n, k]q, a simple counting argument shows that for any integer 0 < g < n, there exists at least one Hamming ball of radius n - g, which contains at least ( gn)/qg-k many codewords. Let ĝ(n, k, q) be the smallest positive integer g such that (gn)/q g-k ≤ 1. One knows that k - 1 ≤ ĝ(n, k, q) ≤ √n(k - 1) ≤ n. For the distance bound up to n - √n(k - 1), it is known that both the list and bounded distance decoding can be solved efficiently. For the distance bound between n - √n(k - 1) and n-ĝ(n, k, q), we do not know whether the Reed-Solomon code is list or bounded distance decodable; nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: (1) List decoding cannot be done for radius n - ĝ(n, k, q) or larger, unless the discrete logarithm over F qĝ(n, k, q)-k is easy. (2) Let h and g be positive integers satisfying q ≥ max(g2, (h - 1)2+ε) and g ≥ (4/ε + 2)(h +1) for a constant ε > 0. We show that the discrete logarithm problem over F qh can be efficiently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g - h]q with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the list decoding problem of Reed-Solomon codes, although the infeasible radius that we obtain is much larger than the radius, which is known to be feasible, it is the first nontrivial bound. Our result on the bounded distance decodability of Reed-Solomon codes is also the first of its kind. The main tools for obtaining these results are an interesting connection between the problem of list decoding of Reed-Solomon code, the problem of a discrete logarithm over finite fields, and a generalization of Katz's theorem on representations of elements in an extension finite field by products of distinct linear factors. © 2007 Society for Industrial and Applied Mathematics.

We consider the following variant of Huffman coding in which the costs of the letters rather than the probabilities of the words, are nonuniform: "Given an alphabet of r letters of nonuniform length, find a minimum-average-length prefix-free set of n codewords over the alphabet"; equivalently, "Find an optimal r-ary search tree with n leaves, where each leaf is accessed with equal probability but the cost to descend from a parent to its ith child depends on i." We show new structural properties of such codes, leading to an O(n log2 r)-time algorithm for finding them. This new algorithm is simpler and faster than the best previously known O(nr min{log n, r})-time algorithm, due to Perl, Garey, and Even [J. Assoc. Comput. Mach., 22 (1975), pp. 202-214].

Given n points in the plane, the degree-K spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for K > 2. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in O(n) time. The results are generalized to points in higher dimensions. It is shown that for any d ≥ 3, an arbitrary collection of points in ℛd contains a spanning tree of degree 3 whose weight is at most 5/3 times the weight of a minimum spanning tree. This is the first paper that achieves factors better than 2 for these problems.

The MEG (minimum equivalent graph) problem is, given a directed graph, tofind a small subset of the edges that maintains all reachability relationsbetween nodes. The problem is NP-hard. This paper gives an approximationalgorithm with performance guarantee of pi^2/6 ~ 1.64. The algorithm and itsanalysis are based on the simple idea of contracting long cycles. (This resultis strengthened slightly in ``On strongly connected digraphs with bounded cyclelength'' (1996).) The analysis applies directly to 2-Exchange, a simple ``localimprovement'' algorithm, showing that its performance guarantee is 1.75.