Authors:Dana Moshkovitz Pages: 531 - 582 Abstract: A long line of work in Theoretical Computer Science shows that a function is close to a low-degree polynomial iff it is locally close to a low-degree polynomial. This is known as low-degree testing and is the core of the algebraic approach to construction of PCP. We obtain a low-degree test whose error, i.e., the probability it accepts a function that does not correspond to a low-degree polynomial, is polynomially smaller than existing low-degree tests. A key tool in our analysis is an analysis of the sampling properties of the incidence graph of degree-k curves and k′-tuples of points in a finite space \({\mathbb{F}^m}\) . We show that the Sliding Scale Conjecture in PCP, namely the conjecture that there are PCP verifiers whose error is exponentially small in their randomness, would follow from a derandomization of our low-degree test. PubDate: 2017-09-01 DOI: 10.1007/s00037-016-0149-4 Issue No:Vol. 26, No. 3 (2017)

Authors:Eric Allender; Anna Gál; Ian Mertz Pages: 583 - 625 Abstract: We consider the complexity class ACC 1 and related families of arithmetic circuits. We prove a variety of collapse results, showing several settings in which no loss of computational power results if fan-in of gates is severely restricted, as well as presenting a natural class of arithmetic circuits in which no expressive power is lost by severely restricting the algebraic degree of the circuits. We draw attention to the strong connections that exist between ACC 1 and VP, via connections to the classes CC 1[m] for various m. These results tend to support a conjecture regarding the computational power of the complexity class VP over finite algebras, and they also highlight the significance of a class of arithmetic circuits that is in some sense dual to VP. In particular, these dual-VP classes provide new characterizations of ACC 1 and TC 1 in terms of circuits of semiunbounded fan-in. As a corollary, we show that ACC i = CC i for all \({i \geq 1}\) . PubDate: 2017-09-01 DOI: 10.1007/s00037-016-0146-7 Issue No:Vol. 26, No. 3 (2017)

Authors:V. Arvind; Johannes Köbler; Gaurav Rattan; Oleg Verbitsky Pages: 627 - 685 Abstract: Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if the color refinement procedure succeeds in distinguishing G from any non-isomorphic graph H. Babai et al. (SIAM J Comput 9(3):628–635, 1980) have shown that random graphs are amenable with high probability. We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time \({O((n+m)\log n)}\) , where n and m denote the number of vertices and the number of edges in the input graph. We use our characterization of amenable graphs to analyze the approach to Graph Isomorphism based on the notion of compact graphs. A graph is called compact if the polytope of its fractional automorphisms is integral. Tinhofer (Discrete Appl Math 30(2–3):253–264, 1991) noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing compact graphs and recognizing them in polynomial time remains an open question. Our results in this direction are summarized below: We show that all amenable graphs are compact. In other words, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement. Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy, and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs. PubDate: 2017-09-01 DOI: 10.1007/s00037-016-0147-6 Issue No:Vol. 26, No. 3 (2017)

Authors:Andrei Gabrielov; Nicolai Vorobjov Pages: 687 - 715 Abstract: We prove that the depth of any arithmetic network for deciding membership in a semialgebraic set \({\Sigma \subset \mathbb{R}^{n}}\) is bounded from below by $$c_1 \sqrt{ \frac{\log ({\rm b}(\Sigma))}{n}} -c_2 \log n,$$ where \({{\rm b}(\Sigma)}\) is the sum of the Betti numbers of \({\Sigma}\) with respect to “ordinary” (singular) homology, and c 1, c 2 are some (absolute) positive constants. This result complements the similar lower bound in Montaña et al. (Appl Algebra Engrg Comm Comput 7:41–51, 1996) for locally closed semialgebraic sets in terms of the sum of Borel–Moore Betti numbers. We also prove that if \({\rho: \mathbb{R}^{n} \to \mathbb{R}^{n-r}}\) is the projection map, for some \({r=0, \ldots, n}\) , then the depth of any arithmetic network deciding membership in \({\Sigma}\) is bounded by $$\frac{c_1\sqrt{\log ({\rm b}(\rho(\Sigma)))}}{n} - c_2 \log n$$ for some positive constants c 1, c 2. PubDate: 2017-09-01 DOI: 10.1007/s00037-016-0145-8 Issue No:Vol. 26, No. 3 (2017)

Authors:Gábor Ivanyos; Youming Qiao; K. V. Subrahmanyam Pages: 717 - 763 Abstract: In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an \({n \times n}\) matrix T with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds’ problem: compute the rank of T over the free skew field. This problem has been proposed, sometimes in disguise, from several different perspectives in the study of, for example, the free skew field itself (Cohn in J Symbol Log 38(2):309–314, 1973), matrix spaces of low rank (Fortin-Reutenauer in Sémin Lothar Comb 52:B52f 2004), Edmonds’ original problem (Gurvits in J Comput Syst Sci 69(3):448–484, 2004), and more recently, non-commutative arithmetic circuits with divisions (Hrubeš and Wigderson in Theory Comput 11:357-393, 2015. doi:10.4086/toc.2015.v011a014). It is known that this problem relates to the following invariant ring, which we call the \({\mathbb{F}}\) -algebra of matrix semi-invariants, denoted as R(n, m). For a field \({\mathbb{F}}\) , it is the ring of invariant polynomials for the action of \({{\rm SL}(n, \mathbb{F}) \times {\rm SL}(n, \mathbb{F})}\) on tuples of matrices— \({(A, C)\in {\rm SL}(n, \mathbb{F}) \times {\rm SL}(n, \mathbb{F})}\) sends \({(B_{1}, \ldots, B_m)\in M(n, \mathbb{F})^{\oplus m}}\) to \({(AB_1 {C}^{{\rm T}}, \ldots, AB_m {C}^{\rm T})}\) . Then those T with non-commutative rank < n correspond to those points in the nullcone of R(n, m). In particular, if the nullcone of R(n, m) is defined by elements of degree \({\leq \sigma}\) , then there follows a \({{\rm poly}(n,\sigma)}\) -time randomized algorithm to decide whether the non-commutative rank of T is full. To our knowledge, previously the best bound for \({\sigma}\) was \({O(n^{2}\cdot 4^{n^2})}\) over algebraically closed fields of characteristic 0 (Derksen in Proc Am Math Soc 129(4):955–964, 2001). We now state the main contributions of this paper: We observe that by using an algorithm of Gurvits, and assuming the above bound \({\sigma}\) for R(n, m) over \({\mathbb{Q}}\) , deciding whether or not T has non-commutative rank < n over \({\mathbb{Q}}\) can be done deterministically in time polynomial in the input size and \({\sigma}\) . When \({\mathbb{F}}\) is large enough, we devise an algorithm for the non-commutative Edmonds pr... PubDate: 2017-09-01 DOI: 10.1007/s00037-016-0143-x Issue No:Vol. 26, No. 3 (2017)

Authors:Evangelos Bampas; Andreas-Nikolas Göbel; Aris Pagourtzis; Aris Tentes Pages: 421 - 467 Abstract: We investigate the complexity of hard (#P-complete) counting problems that have easy decision version. By ‘easy decision,’ we mean that deciding whether the result of counting is nonzero is in P. This property is shared by several well-known problems, such as counting the number of perfect matchings in a given graph or counting the number of satisfying assignments of a given DNF formula. We focus on classes of such hard-to-count easy-to-decide problems which emerged through two seemingly disparate approaches: one taken by Hemaspaandra et al. (SIAM J Comput 36(5):1264–1300, 2007), who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. (Lect Notes Comput Sci 2563:453–463, 2001), who defined the classTotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined by Hemaspaandra et al., but are unlikely to be complete for these classes under reductions under which these classes are downward closed, e.g., parsimonious reductions. This, applied to the #MONSAT problem, partially answers an open question of Hemaspaandra et al. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains hard counting problems. PubDate: 2017-06-01 DOI: 10.1007/s00037-016-0137-8 Issue No:Vol. 26, No. 2 (2017)

Authors:Eric Allender; Dhiraj Holden; Valentine Kabanets Pages: 469 - 496 Abstract: We consider variants of the minimum circuit size problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MSCP QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC 0 under uniform AC 0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures. PubDate: 2017-06-01 DOI: 10.1007/s00037-016-0124-0 Issue No:Vol. 26, No. 2 (2017)

Authors:Ishay Haviv; Ning Xie Pages: 497 - 530 Abstract: A function \({f : {\mathbb F}_{2}^{n} \rightarrow {\{0,1\}}}\) is triangle-free if there are no \({x_{1},x_{2},x_{3} \in {\mathbb F}_{2}^{n}}\) satisfying \({x_{1} + x_{2} + x_{3} = 0}\) and \({f(x_{1}) = f(x_{2}) = f(x_{3}) = 1}\) . In testing triangle-freeness, the goal is to distinguish with high probability triangle-free functions from those that are \({\varepsilon}\) -far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on \({\varepsilon}\) (Green 2005); however, the best-known upper bound is a tower-type function of \({1/\varepsilon}\) . The best known lower bound on the query complexity of the canonical tester is \({1/\varepsilon^{13.239}}\) (Fu & Kleinberg 2014). In this work we introduce a new approach to proving lower bounds on the query complexity of triangle-freeness. We relate the problem to combinatorial questions on collections of vectors in \({{\mathbb Z}_D^n}\) and to sunflower conjectures studied by Alon, Shpilka & Umans (2013). The relations yield that a refutation of the Weak Sunflower Conjecture over \({{\mathbb Z}_{4}}\) implies a super-polynomial lower bound on the query complexity of the canonical tester for triangle-freeness. Our results are extended to testing k-cycle-freeness of functions with domain \({{\mathbb F}_p^n}\) for every \({k \ge 3}\) and a prime p. In addition, we generalize the lower bound of Fu and Kleinberg to k-cycle-freeness for \({k \geq 4}\) by generalizing the construction of uniquely solvable puzzles due to Coppersmith & Winograd (1990). PubDate: 2017-06-01 DOI: 10.1007/s00037-016-0138-7 Issue No:Vol. 26, No. 2 (2017)

Authors:Alexander Razborov Abstract: We show that the total space in resolution, as well as in any other reasonable proof system, is equal (up to a polynomial and \({(\log n)^{O(1)}}\) factors) to the minimum refutation depth. In particular, all these variants of total space are equivalent in this sense. The same conclusion holds for variable space as long as we penalize for excessively (that is, super-exponential) long proofs, which makes the question about equivalence of variable space and depth about the same as the question of (non)-existence of “supercritical” tradeoffs between the variable space and the proof length. We provide a partial negative answer to this question: for all \({s(n) \leq n^{1/2}}\) there exist CNF contradictions \({\tau_n}\) that possess refutations with variable space s(n) but such that every refutation of \({\tau_n}\) with variable space \({o(s^2)}\) must have double exponential length \({2^{2^{\Omega(s)}}}\) . We also include a much weaker tradeoff result between variable space and depth in the opposite range \({s(n) \ll \log n}\) and show that no supercritical tradeoff is possible in this range. PubDate: 2017-10-17 DOI: 10.1007/s00037-017-0163-1

Authors:Leslie Ann Goldberg; Heng Guo Abstract: We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our results are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum computations as evaluations of classical partition functions. These results rely on interesting and deep results about quantum computation in order to obtain hardness results about the difficulty in (classically) evaluating the partition functions for certain fixed parameters. The motivation for this paper is to study more comprehensively the complexity of (classically) approximating the Ising and Tutte partition functions with complex parameters. Partition functions are combinatorial in nature, and quantifying their approximation complexity does not require a detailed understanding of quantum computation. Using combinatorial arguments, we give the first full classification of the complexity of multiplicatively approximating the norm and additively approximating the argument of the Ising partition function for complex edge interactions (as well as of approximating the partition function according to a natural complex metric). We also study the norm approximation problem in the presence of external fields, for which we give a complete dichotomy when the parameters are roots of unity. Previous results were known just for a few such points, and we strengthen these results from BQP-hardness to #P-hardness. Moreover, we show that computing the sign of the Tutte polynomial is #P-hard at certain points related to the simulation of BQP. Using our classifications, we then revisit the connections to quantum computation, drawing conclusions that are a little different from (and incomparable to) ones in the quantum literature, but along similar lines. PubDate: 2017-09-13 DOI: 10.1007/s00037-017-0162-2

Authors:Leslie G. Valiant Abstract: We define the notion of diversity for families of finite functions and express the limitations of a simple class of holographic algorithms, called elementary algorithms, in terms of limitations on diversity. We show that this class of elementary algorithms is too weak to solve the Boolean circuit value problem, or Boolean satisfiability, or the permanent. The lower bound argument is a natural but apparently novel combination of counting and algebraic dependence arguments that is viable in the holographic framework. We go on to describe polynomial time holographic algorithms that go beyond the elementarity restriction in the two respects that they use exponential size fields, and multiple oracle calls in the form of polynomial interpolation. These new algorithms, which use bases of three components, compute the parity of the following quantities for degree three planar undirected graphs: the number of 3-colorings up to permutation of colors, the number of connected vertex covers, and the number of induced forests or feedback vertex sets. In each case, the parity can also be computed for any one slice of the problem, in particular for colorings where the first color is used a certain number of times, or where the connected vertex cover, feedback set or induced forest has a certain number of nodes. PubDate: 2017-08-29 DOI: 10.1007/s00037-017-0160-4

Authors:Badih Ghazi; Ilan Komargodski; Pravesh K. Kothari; Madhu Sudan Abstract: We introduce a simple model illustrating the utility of context in compressing communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information \({X \in \{0,1\}^n}\) and Bob gets \({Y \in \{0,1\}^n}\) , where (X, Y) is drawn from a known distribution, and Bob wishes to compute some function g(X, Y) or some close approximation to it (i.e., the output is g(X, Y) with high probability over (X, Y)). In our variant, Alice does not know g, but only knows some function f which is a very close approximation to g. Thus, the function being computed forms the context for the communication. It is an enormous implicit input, potentially described by a truth table of size 2 n . Imprecise knowledge of this function models the (mild) uncertainty in this context. We show that uncertainty can lead to a huge cost in communication. Specifically, we construct a distribution \({\mu}\) over \({(X,Y)\in \{0,1\}^n \times \{0,1\}^n}\) and a class of function pairs (f, g) which are very close (i.e., disagree with o(1) probability when (X, Y) are sampled according to \({\mu}\) ), for which the communication complexity of f or g in the standard setting is one bit, whereas the (two-way) communication complexity in the uncertain setting is at least \({\Omega(\sqrt{n})}\) bits even when allowing a constant probability of error. It turns out that this blow-up in communication complexity can be attributed in part to the mutual information between X and Y. In particular, we give an efficient protocol for communication under contextual uncertainty that incurs only a small blow-up in communication if this mutual information is small. Namely, we show that if g has a communication protocol with complexity k in the standard setting and the mutual information between X and Y is I, then g has a one-way communication protocol with complexity \({O((1+I)\cdot 2^k)}\) in the uncertain setting. This result is an immediate corollary of an even stronger result which shows that if g has one-way communication complexity k, then it has one-way uncertain-communication complexity at most \({O((1+I)\cdot k)}\) . In the particular case where the input distribution is a product distribution (and so I = 0), the protocol in the uncertain setting only incurs a constant factor blow-up in one-way communication and error. PubDate: 2017-08-29 DOI: 10.1007/s00037-017-0161-3

Authors:Christian Ikenmeyer; Ketan D. Mulmuley; Michael Walter Abstract: We show that the problem of deciding positivity of Kronecker coefficients is NP-hard. Previously, this problem was conjectured to be in P, just as for the Littlewood–Richardson coefficients. Our result establishes in a formal way that Kronecker coefficients are more difficult than Littlewood–Richardson coefficients, unless P = NP. We also show that there exists a #P-formula for a particular subclass of Kronecker coefficients whose positivity is NP-hard to decide. This is an evidence that, despite the hardness of the positivity problem, there may well exist a positive combinatorial formula for the Kronecker coefficients. Finding such a formula is a major open problem in representation theory and algebraic combinatorics. Finally, we consider the existence of the partition triples \({(\lambda, \mu, \pi)}\) such that the Kronecker coefficient \({k^\lambda_{\mu, \pi} = 0}\) but the Kronecker coefficient \({k^{l\lambda}_{l \mu, l \pi} > 0}\) for some integer l > 1. Such “holes” are of great interest as they witness the failure of the saturation property for the Kronecker coefficients, which is still poorly understood. Using insight from computational complexity theory, we turn our hardness proof into a positive result: We show that not only do there exist many such triples, but they can also be found efficiently. Specifically, we show that, for any \({0 < \epsilon \leq 1}\) , there exists \({0 < a < 1}\) such that, for all m, there exist \({\Omega(2^{m^a})}\) partition triples \({(\lambda,\mu,\mu)}\) in the Kronecker cone such that: (a) the Kronecker coefficient \({k^\lambda_{\mu,\mu}}\) is zero, (b) the height of \({\mu}\) is m, (c) the height of \({\lambda}\) is \({\leq m^\epsilon}\) , and (d) \({ \lambda = \mu \le m^3}\) . The proof of the last result illustrates the effectiveness of the explicit proof strategy of GCT. PubDate: 2017-07-27 DOI: 10.1007/s00037-017-0158-y

Authors:Irit Dinur; Or Meir Abstract: One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de Morgan formulas. Karchmer et al. (Comput Complex 5(3/4):191–204, 1995b) suggested to approach this problem by proving that formula complexity behaves “as expected” with respect to the composition of functions \({f\diamond g}\) . They showed that this conjecture, if proved, would imply super-polynomial formula lower bounds. The first step toward proving the KRW conjecture was made by Edmonds et al. (Comput Complex 10(3):210–246, 2001), who proved an analogue of the conjecture for the composition of “universal relations.” In this work, we extend the argument of Edmonds et al. (2001) further to \({f\diamond g}\) where f is an arbitrary function and g is the parity function. While this special case of the KRW conjecture was already proved implicitly in Håstad’s work on random restrictions (Håstad in SIAM J Comput 27(1):48–64, 1998), our proof seems more likely to be generalizable to other cases of the conjecture. In particular, our proof uses an entirely different approach, based on communication complexity technique of Karchmer & Wigderson in (SIAM J Discrete Math 3(2):255–265, 1990). In addition, our proof gives a new structural result, which roughly says that the naive way for computing \({f\diamond g}\) is the only optimal way. Along the way, we obtain a new proof of the state-of-the-art formula lower bound of n 3-o(1) due to Håstad (1998). PubDate: 2017-07-27 DOI: 10.1007/s00037-017-0159-x

Authors:John M. Hitchcock; Hadi Shafei Abstract: We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following: For every \({k \geq 2}\) , there is a k-T-complete set for NP that is k-T-autoreducible, but is not k-tt-autoreducible or (k − 1)-T-autoreducible. For every \({k \geq 3}\) , there is a k-tt-complete set for NP that is k-tt-autoreducible, but is not (k − 1)-tt-autoreducible or (k − 2)-T-autoreducible. There is a tt-complete set for NP that is tt-autoreducible, but is not btt-autoreducible. Under the stronger assumption that there is a p-generic set in NP \({\cap}\) coNP, we show: For every \({k \geq 2}\) , there is a k-tt-complete set for NP that is k-tt-autoreducible, but is not (k − 1)-T-autoreducible. Our proofs are based on constructions from separating NP-completeness notions. For example, the construction of a 2-T-complete set for NP that is not 2-tt-complete also separates 2-T-autoreducibility from 2-tt-autoreducibility. PubDate: 2017-07-18 DOI: 10.1007/s00037-017-0157-z

Authors:Benjamin Rossman Abstract: We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity \({O(\frac{1}{d} \log s)^d}\) . In particular, this gives a tight \({2^{\Omega(d(n^{1/d}-1))}}\) lower bound on the size of depth d + 1 formulas computing the parity function. These results strengthen the corresponding \({2^{\Omega(n^{1/d})}}\) and \({O(\log s)^d}\) bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner. PubDate: 2017-07-05 DOI: 10.1007/s00037-017-0156-0

Authors:Emanuele Viola; Avi Wigderson Abstract: A map \({f : \{0,1\}^{n} \to \{0,1\}^{n}}\) has locality t if every output bit of f depends only on t input bits. Arora et al. (Colloquium on automata, languages and programming, ICALP, 2009) asked if there exist bounded-degree expander graphs on 2 n nodes such that the neighbors of a node \({x\in\{0,1\}^{n}}\) can be computed by maps of constant locality. We give an explicit construction of such graphs with locality one. We then give three applications of this construction: (1) lossless expanders with constant locality, (2) more efficient error reduction for randomized algorithms, and (3) more efficient hardness amplification of one-way permutations. We also give, for n of the form \({n=4\cdot3^{t}}\) , an explicit construction of bipartite Ramanujan graphs of degree 3 with 2 n −1 nodes in each side such that the neighbors of a node \({x\in \{0,1\}^{n}{\setminus} \{0^{n}\}}\) can be computed either (1) in constant locality or (2) in constant time using standard operations on words of length \({\Omega(n)}\) . Our results use in black-box fashion deep explicit constructions of Cayley expander graphs, by Kassabov (Invent Math 170(2):327–354, 2007) for the symmetric group \({S_{n}}\) and by Morgenstern (J Comb Theory Ser B 62(1):44–62, 1994) for the special linear group SL \({(2,F_{2^{n}})}\) . PubDate: 2017-06-20 DOI: 10.1007/s00037-017-0155-1

Authors:Frederic Green; Daniel Kreymer; Emanuele Viola Abstract: We show that degree-d block-symmetric polynomials in n variables modulo any odd p correlate with parity exponentially better than degree-d symmetric polynomials, if \({n \ge cd^2 {\rm log} d}\) and \({d \in [0.995 \cdot p^t - 1,p^t)}\) for some \({t \ge 1}\) and some \({c > 0}\) that depends only on p. For these infinitely many degrees, our result solves an open problem raised by a number of researchers including Alon & Beigel (IEEE conference on computational complexity (CCC), pp 184–187, 2001). The only previous case for which this was known was d = 2 and p = 3 (Green in J Comput Syst Sci 69(1):28–44, 2004). The result is obtained through the development of a theory we call spectral analysis of symmetric correlation, which originated in works of Cai et al. (Math Syst Theory 29(3):245–258, 1996) and Green (Theory Comput Syst 32(4):453–466, 1999). In particular, our result follows from a detailed analysis of the correlation of symmetric polynomials, which is determined up to an exponentially small relative error when \({d = p^t-1}\) . PubDate: 2017-04-05 DOI: 10.1007/s00037-017-0153-3

Authors:Elena Grigorescu; Chris Peikert Abstract: The question of list-decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete linear structure of linear codes and point lattices in \({\mathbb{R}^{N}}\) , and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the study of list decoding for lattices. Namely: for a lattice \({\mathcal{L}\subseteq \mathbb{R}^N}\) , given a target vector \({r \in \mathbb{R}^N}\) and a distance parameter d, output the set of all lattice points \({w \in \mathcal{L}}\) that are within distance d of r. In this work, we focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of Barnes–Wall lattices. Our main contributions are twofold: We give tight combinatorial bounds on the worst-case list size, showing it to be polynomial in the lattice dimension for any error radius bounded away from the lattice’s minimum distance (in the Euclidean norm). We use our combinatorial bounds to generalize the unique-decoding algorithm of Micciancio and Nicolosi (IEEE International Symposium on Information Theory 2008) to work beyond the unique-decoding radius and still run in polynomial time up to the list-decoding radius. Just like the Micciancio–Nicolosi algorithm, our algorithm is highly parallelizable, and with sufficiently many processors, it can run in parallel time only poly-logarithmic in the lattice dimension. PubDate: 2017-01-12 DOI: 10.1007/s00037-016-0151-x

Abstract: We show that approximating the second eigenvalue of stochastic operators is BPL-complete, thus giving a natural problem complete for this class. We also show that approximating any eigenvalue of a stochastic and Hermitian operator with constant accuracy can be done in BPL. This work together with related work on the subject reveal a picture where the various space-bounded classes (e.g., probabilistic logspace, quantum logspace and the class DET) can be characterized by algebraic problems (such as approximating the spectral gap) where, roughly speaking, the difference between the classes lies in the kind of operators they can handle (e.g., stochastic, Hermitian or arbitrary). PubDate: 2016-12-16 DOI: 10.1007/s00037-016-0150-y