Authors:Evangelos Bampas; Andreas-Nikolas Göbel; Aris Pagourtzis; Aris Tentes Pages: 421 - 467 Abstract: 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: 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: 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:Igor Pak; Greta Panova Pages: 1 - 36 Abstract: Abstract We study the complexity of computing Kronecker coefficients \({g(\lambda,\mu,\nu)}\) . We give explicit bounds in terms of the number of parts \({\ell}\) in the partitions, their largest part size N and the smallest second part M of the three partitions. When M = O(1), i.e., one of the partitions is hook-like, the bounds are linear in log N, but depend exponentially on \({\ell}\) . Moreover, similar bounds hold even when \({M=e^{O(\ell)}}\) . By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(log N) time for a bounded number \({\ell}\) of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook and computing characters of S n are also considered. PubDate: 2017-03-01 DOI: 10.1007/s00037-015-0109-4 Issue No:Vol. 26, No. 1 (2017)

Authors:Eli Ben-Sasson; Noga Ron-Zewi; Madhu Sudan Pages: 37 - 77 Abstract: Abstract We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field \({\mathbb{F}_q}\) and an extension field \({\mathbb{F}_{q^n}}\) , a property is a set of functions mapping \({\mathbb{F}_{q^n}}\) to \({\mathbb{F}_q}\) . The property is said to be affine-invariant if it is invariant under affine transformations of \({\mathbb{F}_{q^n}}\) , linear if it is an \({\mathbb{F}_q}\) -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties. PubDate: 2017-03-01 DOI: 10.1007/s00037-015-0115-6 Issue No:Vol. 26, No. 1 (2017)

Authors:Barış Aydınlıoğlu; Dieter van Melkebeek Pages: 79 - 118 Abstract: Abstract In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in any way implies the ability to do so in the canonical way through pseudorandom generators. For the setting of decision problems, Impagliazzo, Kabanets, and Wigderson (2002) implicitly showed the following equivalence: Randomized polynomial-time decision procedures for promise problems can be simulated in \({\sf{NSUBEXP}}\) (the subexponential version of \({\sf{NP}}\) ) with subpolynomial advice on infinitely many input lengths if and only if \({{\sf{NEXP}} \not \subseteq }\) \({\sf{P}/ poly}\) . We establish a full analog in the setting of verification procedures: Arthur-Merlin games for promise problems can be simulated in \({{\sf{\Sigma_{2} SUBEXP}}}\) (the subexponential version of \({\sf{\Sigma_{2} P}}\) ) with subpolynomial advice on infinitely many input lengths if and only if \({\sf{\Sigma_2EXP} \not \subseteq }\) \({\sf{NP}/poly}\) . A key ingredient in our proofs is improved Karp-Lipton style collapse results for nondeterministic circuits. The following are two instantiations that may be of independent interest: Assuming that Arthur-Merlin games can be derandomized in \({{\sf{\Sigma_{2}} P}}\) , we show that (i) \({\sf{PSPACE} \subseteq }\) \({\sf{NP/poly}}\) implies \({\sf{PSPACE} \subseteq \sf{\Sigma_2P}}\) and (ii) \({\sf{coNP} \subseteq {\sf{NP/poly}}}\) implies \({{\sf{PH} \subseteq \sf{P^{\Sigma_2P}}}}\) . Of possible independent interest is a generic framework that we provide, which captures several results in the literature of the form “derandomization implies circuit lower bounds.” In particular, our framework enables a unified view of our result, the one by Impagliazzo et al. (2002) mentioned above, as well as the result by Kabanets and Impagliazzo (2004) that derandomizing polynomial identity testing yields arithmetic circuit lower bounds. PubDate: 2017-03-01 DOI: 10.1007/s00037-014-0095-y Issue No:Vol. 26, No. 1 (2017)

Authors:Salman Beigi; Omid Etesami; Amin Gohari Pages: 119 - 145 Abstract: Abstract “Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity. If k instances of a decision problem can be efficiently solved using \({\ell < k}\) help bits, then without access to help bits one can efficiently compute a k-bit vector that is not equal to the k-bit vector of solutions to the k instances. A decision problem with this property is called k-membership comparable. Amir, Beigel, and Gasarch (1990) show that for constant k, all k-membership comparable languages are in P/poly. We extend this result to the setting of randomized computation: We show that for k at most logarithmic, the decision problem is k-membership comparable if using \({\ell}\) help bits, k instances of the problem can be efficiently solved with probability greater than \({2^{\ell-k}}\) . The same conclusion holds if using less than \({k(1 - h(\alpha))}\) help bits (where \({h(\cdot)}\) is the binary entropy function), we can efficiently solve \({1-\alpha}\) fraction of the instances correctly with non-vanishing probability. We note that when k is constant, k-membership comparability implies being in P/poly. Next we consider the setting of average-case complexity: Assume that we can solve k instances of a decision problem using some help bits whose entropy is less than k when the k instances are drawn independently from a particular distribution. Then we can efficiently solve an instance drawn from that distribution with probability better than 1/2. Finally, we show that in the case where k is super-logarithmic, assuming k-membership comparability of a decision problem, one cannot prove that the problem is in P/poly by a “relativizing" proof technique. All previous known proofs in this area have been relativizing. PubDate: 2017-03-01 DOI: 10.1007/s00037-016-0135-x Issue No:Vol. 26, No. 1 (2017)

Authors:Gábor Braun; Rahul Jain; Troy Lee; Sebastian Pokutta Pages: 147 - 197 Abstract: Abstract Common information was introduced by Wyner (IEEE Trans Inf Theory 21(2):163–179, 1975) as a measure of dependence of two random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix in Braun and Pokutta (Proceedings of FOCS, 2013) and Jain et al. (Proceedings of SODA, 2013). Lower bounds on nonnegative rank have important applications to several areas such as communication complexity and combinatorial optimization. We begin a systematic study of common information extending the dual characterization of Witsenhausen (SIAM J Appl Math 31(2):313–333, 1976). Our main results are: (i) Common information is additive under tensoring of matrices. (ii) It characterizes the (logarithm of the) amortized nonnegative rank of a matrix, i.e., the minimal nonnegative rank under tensoring and small \({\ell_1}\) perturbations. We also provide quantitative bounds generalizing previous asymptotic results by Wyner (IEEE Trans Inf Theory 21(2):163–179, 1975). (iii) We deliver explicit witnesses from the dual problem for several matrices leading to explicit lower bounds on common information, which are robust under \({\ell_1}\) perturbations. This includes improved lower bounds for perturbations of the all important unique disjointness partial matrix, as well as new insights into its information-theoretic structure. PubDate: 2017-03-01 DOI: 10.1007/s00037-016-0125-z Issue No:Vol. 26, No. 1 (2017)

Authors:Rahul Jain; Zhaohui Wei; Penghui Yao; Shengyu Zhang Pages: 199 - 228 Abstract: Abstract The concepts of quantum correlation complexity and quantum communication complexity were recently proposed to quantify the minimum amount of resources needed in generating bipartite classical or quantum states in the single-shot setting. The former is the minimum size of the initially shared state \({\sigma}\) on which local operations by the two parties (without communication) can generate the target state \({\rho}\) , and the latter is the minimum amount of communication needed when initially sharing nothing. In this paper, we generalize these two concepts to multipartite cases, for both exact and approximate state generation. Our results are summarized as follows. For multipartite pure states, the correlation complexity can be completely characterized by local ranks of sybsystems. We extend the notion of PSD-rank of matrices to that of tensors, and use it to bound the quantum correlation complexity for generating multipartite classical distributions. For generating multipartite mixed quantum states, communication complexity is not always equal to correlation complexity (as opposed to bipartite case). But they differ by at most a factor of 2. Generating a multipartite mixed quantum state has the same communication complexity as generating its optimal purification. But the correlation complexities of these two tasks can be different (though still related by less than a factor of 2). To generate a bipartite classical distribution P(x, y) approximately, the quantum communication complexity is completely characterized by the approximate PSD-rank of P. The quantum correlation complexity of approximately generating multipartite pure states is bounded by approximate local ranks. PubDate: 2017-03-01 DOI: 10.1007/s00037-016-0126-y Issue No:Vol. 26, No. 1 (2017)

Authors:Amir Shpilka; Avishay Tal; Ben lee Volk Pages: 229 - 273 Abstract: Abstract In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is \({\ \hat{f}\ _1 = \sum_{\alpha} \hat{f}(\alpha) }\) ). Specifically, we prove the following results for functions \({f : \{0, 1\}^n \to \{0, 1\}}\) with \({\ \hat{f}\ _1 = A}\) . There is an affine subspace V of co-dimension at most A 2 such that \({f _V}\) is constant. f can be computed by a parity decision tree of size at most \({2^{A^2} n^{2A}}\) . (A parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) f can be computed by a De Morgan formula of size \({O(2^{A^2} n^{2A + 2})}\) and by a De Morgan formula of depth \({O(A^2 + \log(n) \cdot A)}\) . If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth at most \({A^2 \log s}\) . For every \({\epsilon > 0}\) there is a parity decision tree of depth \({O(A^2 + \log(1/\epsilon))}\) and size \({2^{O(A^2)} \cdot \min \{1/\epsilon^2, \log(1/\epsilon)^{2A}\}}\) that \({\epsilon}\) -approximates f. Furthermore, this tree can be learned (in the uniform distribution model), with probability \({1 - \delta}\) , using \({{\tt poly}(n, {\rm exp}(A^2), 1/\epsilon, \log(1/\delta))}\) membership queries. All the results above (except 3) also hold (with a slight change in parameters) for functions \({f : \mathbb{Z}_p^n \to \{0, 1\}}\) . PubDate: 2017-03-01 DOI: 10.1007/s00037-015-0110-y Issue No:Vol. 26, No. 1 (2017)

Authors:Russell Impagliazzo; Valentine Kabanets Pages: 275 - 321 Abstract: Abstract For a class \({\mathcal{F}}\) of formulas (general de Morgan or read-once de Morgan), the shrinkage exponent \({\Gamma_{\mathcal{F}}}\) is the parameter measuring the reduction in size of a formula \({F\in\mathcal{F}}\) after \({F}\) is hit with a random restriction. A Boolean function \({f\colon \{0,1\}^n\to\{1,-1\}}\) is Fourier-concentrated if, when viewed in the Fourier basis, \({f}\) has most of its total mass on “low-degree” coefficients. We show a direct connection between the two notions by proving that shrinkage implies Fourier concentration: For a shrinkage exponent \({\Gamma_{\mathcal{F}}}\) , a formula \({F\in\mathcal{F}}\) of size \({s}\) will have most of its Fourier mass on the coefficients of degree up to about \({s^{1/\Gamma_{\mathcal{F}}}}\) . More precisely, for a Boolean function \({f\colon\{0,1\}^n\to\{1,-1\}}\) computable by a formula of (large enough) size \({s}\) and for any parameter \({r > 0}\) , $$\sum_{A\subseteq [n]\; :\; A \geq s^{1/\Gamma} \cdot r} \hat{f}(A)^2\leq s\cdot{\mathscr{polylog}}(s)\cdot exp\left(-\frac{r^{\frac{\Gamma}{\Gamma-1}}}{s^{o(1)}} \right),$$ where \({\Gamma}\) is the shrinkage exponent for the corresponding class of formulas: \({\Gamma=2}\) for de Morgan formulas, and \({\Gamma=1/\log_2(\sqrt{5}-1)\approx 3.27}\) for read-once de Morgan formulas. This Fourier concentration result is optimal, to within the \({o(1)}\) term in the exponent of \({s}\) . As a standard application of these Fourier concentration results, we get that subquadratic-size de Morgan formulas have negligible correlation with parity. We also show the tight \({\Theta(s^{1/\Gamma})}\) bound on the average sensitivity of read-once formulas of size \({s}\) , which mirrors the known tight bound \({\Theta(\sqrt{s})}\) on the average sensitivity of general de Morgan \({s}\) -size formulas. PubDate: 2017-03-01 DOI: 10.1007/s00037-016-0134-y Issue No:Vol. 26, No. 1 (2017)

Authors:John M. Hitchcock; Hadi Shafei Abstract: 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: 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: 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:Bruno Bauwens; Anton Makhlin; Nikolay Vereshchagin; Marius Zimand Abstract: Abstract Given a machine U, a c-short program for x is a string p such that U(p) = x and the length of p is bounded by c + (the length of a shortest program for x). We show that for any standard Turing machine, it is possible to compute in polynomial time on input x a list of polynomial size guaranteed to contain a \({\operatorname{O}\bigl({\mathrm{log}} x \bigr)}\) -short program for x. We also show that there exists a computable function that maps every x to a list of size x 2 containing a \({\operatorname{O}\bigl(1\bigr)}\) -short program for x. This is essentially optimal because we prove that for each such function there is a c and infinitely many x for which the list has size at least c x 2. Finally we show that for some standard machines, computable functions generating lists with 0-short programs must have infinitely often list sizes proportional to 2 x . PubDate: 2017-04-19 DOI: 10.1007/s00037-017-0154-2

Authors:Massimo Lauria; Jakob Nordström Abstract: Abstract We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size \({n^{\Omega{(d)}}}\) for values of d = d(n) from constant all the way up to \({n^{\delta}}\) for some universal constant \({\delta}\) . This shows that the \({{n^{{\rm O}{(d)}}}}\) running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in Krajíček (Arch Math Log 43(4):427–441, 2004) and Dantchev & Riis (Proceedings of the 17th international workshop on computer science logic (CSL ’03), 2003) and then applying a restriction argument as in Atserias et al. (J Symb Log 80(2):450–476, 2015; ACM Trans Comput Log 17:19:1–19:30, 2016). This yields a generic method of amplifying SOS degree lower bounds to size lower bounds and also generalizes the approach used in Atserias et al. (2016) to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali–Adams from lower bounds on width, degree, and rank, respectively. PubDate: 2017-04-19 DOI: 10.1007/s00037-017-0152-4

Authors:Frederic Green; Daniel Kreymer; Emanuele Viola Abstract: 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: 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

Authors:Dana Moshkovitz Abstract: 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: 2016-12-19 DOI: 10.1007/s00037-016-0149-4

Abstract: 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