Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > L:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

L
TR17-033 | 19th February 2017
Daniel Kane, Shachar Lovett, Sankeerth Rao

#### Labeling the complete bipartite graph with no zero cycles

Revisions: 2

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... more >>>

TR04-002 | 8th January 2004
Troy Lee, Dieter van Melkebeek, Harry Buhrman

#### Language Compression and Pseudorandom Generators

The language compression problem asks for succinct descriptions of
the strings in a language A such that the strings can be efficiently
recovered from their description when given a membership oracle for
A. We study randomized and nondeterministic decompression schemes
and investigate how close we can get to the information ... more >>>

TR05-152 | 9th December 2005
Oded Lachish, Ilan Newman

#### Languages that are Recognized by Simple Counter Automata are not necessarily Testable

Combinatorial property testing deals with the following relaxation of
decision problems: Given a fixed property and an input $f$, one wants
to decide whether $f$ satisfies the property or is far' from satisfying
the property.
It has been shown that regular languages are testable,
and that there exist context free ... more >>>

TR04-014 | 26th November 2003
Chris Pollett

#### Languages to diagonalize against advice classes

Variants of Kannan's Theorem are given where the circuits of
the original theorem are replaced by arbitrary recursively presentable
classes of languages that use advice strings and satisfy certain mild
conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$
does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does
not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ... more >>>

TR06-117 | 31st August 2006
Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

#### Languages with Bounded Multiparty Communication Complexity

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

TR12-052 | 27th April 2012

#### Languages with Efficient Zero-Knowledge PCPs are in SZK

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

TR12-042 | 17th April 2012
Chris Beck, Russell Impagliazzo, Shachar Lovett

#### Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

TR11-066 | 25th April 2011
Venkatesan Guruswami, Ali Kemal Sinop

#### Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

TR12-089 | 7th July 2012
Meena Boppana

#### Lattice Variant of the Sensitivity Conjecture

The Sensitivity Conjecture, posed in 1994, states that the fundamental measures known as the sensitivity and block sensitivity of a Boolean function $f$, $s(f)$ and $bs(f)$ respectively, are polynomially related. It is known that $bs(f)$ is polynomially related to important measures in computer science including the decision-tree depth, polynomial degree, ... more >>>

TR06-147 | 27th November 2006
Chris Peikert, Alon Rosen

#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

We demonstrate an \emph{average-case} problem which is as hard as
finding $\gamma(n)$-approximate shortest vectors in certain
$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n) = O(\sqrt{\log n})$. The previously best known factor for any class
of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

TR04-113 | 19th November 2004
Mårten Trolin

#### Lattices with Many Cycles Are Dense

We give a method for approximating any $n$-dimensional
lattice with a lattice $\Lambda$ whose factor group
$\mathbb{Z}^n / \Lambda$ has $n-1$ cycles of equal length
with arbitrary precision. We also show that a direct
consequence of this is that the Shortest Vector Problem and the Closest
Vector Problem cannot ... more >>>

TR14-129 | 10th October 2014
Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski

#### Leakage-resilient non-malleable codes

Revisions: 1

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this ... more >>>

TR10-074 | 20th April 2010
Parikshit Gopalan, Rocco Servedio

#### Learning and Lower Bounds for AC$^0$ with Threshold Gates

In 2002 Jackson et al. [JKS02] asked whether AC0 circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong Fourier concentration; hence the low-degree algorithm of Linial, Mansour and Nisan ... more >>>

TR14-144 | 30th October 2014
Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

#### Learning circuits with few negations

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

TR11-115 | 8th August 2011

#### Learning Hurdles for Sleeping Experts

We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the ... more >>>

TR05-088 | 3rd August 2005
Jan Arpe

#### Learning Juntas in the Presence of Noise

The combination of two major challenges in machine learning is investigated: dealing with large amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that depend on a small number of variables---so-called juntas---can be learned efficiently from random examples corrupted by random ... more >>>

TR96-008 | 22nd January 1996
F. Bergadano, N.H. Bshouty, Stefano Varricchio

#### Learning Multivariate Polynomials from Substitution and Equivalence Queries

It has been shown in previous recent work that
multiplicity automata are predictable from multiplicity
and equivalence queries. In this paper we generalize
related notions in a matrix representation
and obtain a basis for the solution
of a number of open problems in learnability theory.
Membership queries are generalized ... more >>>

TR00-069 | 14th July 2000
Peter Auer

#### Learning Nested Differences in the Presence of Malicious Noise

We present a PAC-learning algorithm and an on-line learning algorithm
for nested differences of intersection-closed classes. Examples of
intersection-closed classes include axis-parallel rectangles,
monomials, and linear sub-spaces. Our PAC-learning algorithm uses a
pruning technique that we rigorously proof correct. As a result we
show that ... more >>>

TR00-055 | 14th July 2000
Peter Auer, Stephen Kwek, Manfred K. Warmuth

#### Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes

We present algorithms for learning depth two neural networks where the
hidden nodes are threshold gates with constant fan-in. The transfer
function of the output node might be more general: we have results for
the cases when the threshold function, the logistic function or the
identity function is ... more >>>

TR09-060 | 4th June 2009
Harry Buhrman, David García-Soriano, Arie Matsliah

#### Learning parities in the mistake-bound model.

We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model.
We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ... more >>>

TR10-066 | 14th April 2010
Sanjeev Arora, Rong Ge

#### Learning Parities with Structured Noise

Revisions: 1

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we
have access to an oracle that, each time we press a button,
returns a random vector $a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as
$a\cdot u +\eta$, where ... more >>>

TR98-060 | 8th October 1998
Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

#### Learning polynomials with queries -- The highly noisy case.

This is a revised version of work which has appeared
in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field
$F$ into $F$,
we consider the task of reconstructing a list of all $n$-variate
degree $d$ polynomials which agree with $f$
more >>>

TR07-129 | 25th October 2007
Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

#### Learning Random Monotone DNF

We give an algorithm that with high probability properly learns random monotone t(n)-term
DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ... more >>>

TR17-046 | 8th March 2017
Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

#### Learning Residual Alternating Automata

Residuality plays an essential role for learning finite automata.
While residual deterministic and nondeterministic
automata have been understood quite well, fundamental
questions concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman have initiated
a systematic study of residual AFAs and proposed an algorithm called AL*
-an extension of ... more >>>

TR10-075 | 22nd April 2010
Ben Reichardt

#### Least span program witness size equals the general adversary lower bound on quantum query complexity

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>

TR09-062 | 28th July 2009
Daniele Venturi

#### Lecture Notes on Algorithmic Number Theory

The principal aim of this notes is to give a survey on the state of the art of algorithmic number theory, with particular focus on the theory of elliptic curves.
Computational security is the goal of modern cryptographic constructions: the security of modern criptographic schemes stems from the assumption ... more >>>

TR06-077 | 12th June 2006
Maria Lopez-Valdes

#### Lempel-Ziv Dimension for Lempel-Ziv Compression

This paper describes the Lempel-Ziv dimension (Hausdorff like
dimension inspired in the LZ78 parsing), its fundamental properties
and relation with Hausdorff dimension.

It is shown that in the case of individual infinite sequences, the
Lempel-Ziv dimension matches with the asymptotical Lempel-Ziv
compression ratio.

This fact is used to describe results ... more >>>

TR05-055 | 19th May 2005
Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

#### Leontief Economies Encode Nonzero Sum Two-Player Games

We give a reduction from any two-player game to a special case of
the Leontief exchange economy, with the property that the Nash equilibria of the game and the
equilibria of the market are in one-to-one correspondence.

Our reduction exposes a potential hurdle inherent in solving certain
families of market ... more >>>

TR11-168 | 9th December 2011
Joshua Grochow

G_2\times\cdots G_t$, where each$G_i$is a cyclic group of size$p^j$for some prime$p$and integer$j\ge 1$. If$a_i$is the generator of the cyclic group of ... more >>> TR14-141 | 24th October 2014 Shachar Lovett #### Linear codes cannot approximate the network capacity within any constant factor Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>> TR99-025 | 2nd July 1999 Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan #### Linear Consistency Testing We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are linear'' if their graphs form straight lines on the plane. Two such functions are consistent'' if the lines have the same slope. We propose a variant of a test of ... more >>> TR05-100 | 30th August 2005 David Zuckerman #### Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>> TR15-017 | 20th January 2015 Bruno Bauwens, Marius Zimand #### Linear list-approximation for short programs (or the power of a few random bits) A$c$-short program for a string$x$is a description of$x$of length at most$C(x) + c$, where$C(x)$is the Kolmogorov complexity of$x$. We show that there exists a randomized algorithm that constructs a list of$n$elements that contains a$O(\log n)$-short program for$x$. ... more >>> TR16-182 | 14th November 2016 Rohit Gurjar, Thomas Thierauf #### Linear Matroid Intersection is in quasi-NC Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size$n^{O(\log n)}$, and$O(\log^2 n)$depth. This generalizes ... more >>> TR07-033 | 14th February 2007 Michael Navon, Alex Samorodnitsky #### Linear programming bounds for codes via a covering argument We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, ... more >>> TR17-086 | 9th May 2017 C Ramya, Raghavendra Rao B V #### Linear Projections of the Vandermonde Polynomial Revisions: 1 An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation ... more >>> TR16-174 | 7th November 2016 Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev #### Linear Sketching over$\mathbb F_2$Revisions: 5 , Comments: 2 We initiate a systematic study of linear sketching over$\mathbb F_2$. For a given Boolean function$f \colon \{0,1\}^n \to \{0,1\}$a randomized$\mathbb F_2$-sketch is a distribution$\mathcal M$over$d \times n$matrices with elements over$\mathbb F_2$such that$\mathcal Mx$suffices for computing$f(x)$with high ... more >>> TR11-048 | 10th April 2011 Arkadev Chattopadhyay, Shachar Lovett #### Linear systems over abelian groups We consider a system of linear constraints over any finite Abelian group$G$of the following form:$\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$for$i=1,\ldots,t$and each$A_i \subset G$,$\ell_{i,j}$is an element of$G$and$x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean ... more >>> TR09-084 | 24th September 2009 Arkadev Chattopadhyay, Avi Wigderson #### Linear systems over composite moduli We study solution sets to systems of generalized linear equations of the following form:$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$, where$\ell_1, \ldots ,\ell_t$are linear forms in$n$Boolean variables, each$A_i$is an arbitrary subset of$\mathbb{Z}_m$, and$m$is a composite ... more >>> TR08-101 | 20th November 2008 Marek Karpinski, Warren Schudy #### Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>> TR11-058 | 15th April 2011 Michael Viderman #### Linear time decoding of regular expander codes Revisions: 1 Sipser and Spielman (IEEE IT, 1996) showed that any$(c,d)$-regular expander code with expansion parameter$> \frac{3}{4}$is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007) proved that expansion parameter$> \frac{2}{3} + \frac{1}{3c}$is sufficient to correct a constant fraction of ... more >>> TR04-016 | 3rd March 2004 Michael Alekhnovich, Eli Ben-Sasson #### Linear Upper Bounds for Random Walk on Small Density Random 3CNFs We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ... more >>> TR12-073 | 11th June 2012 Venkatesan Guruswami, Carol Wang #### Linear-algebraic list decoding for variants of Reed-Solomon codes Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and list error-correction capability. Specifically, for any$\epsilon > 0$, Guruswami and Rudra presented an$n^{O(1/\epsilon)}$time algorithm to list decode appropriate folded RS codes of rate$R$from a fraction$1-R-\epsilon$of ... more >>> TR14-015 | 24th January 2014 Jack H. Lutz, Neil Lutz #### Lines Missing Every Random Point Revisions: 1 This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0. more >>> TR14-007 | 17th January 2014 Mark Braverman, Klim Efremenko #### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise In this paper we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient to a noise rate of up to$1/2-\varepsilon$, ... more >>> TR11-165 | 8th December 2011 Elena Grigorescu, Chris Peikert #### List Decoding Barnes-Wall Lattices Revisions: 2 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 structure of linear codes and point lattices in$R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>> TR14-087 | 12th July 2014 Abhishek Bhowmick, Shachar Lovett #### List decoding Reed-Muller codes over small fields Revisions: 1 The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a finite field$\mathbb{F}$. ... more >>> TR12-146 | 7th November 2012 Venkatesan Guruswami, Chaoping Xing #### List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>> TR08-105 | 26th November 2008 Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra #### List Decoding Tensor Products and Interleaved Codes We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. 1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>> TR03-042 | 15th May 2003 Luca Trevisan #### List Decoding Using the XOR Lemma We show that Yao's XOR Lemma, and its essentially equivalent rephrasing as a Direct Product Lemma, can be re-interpreted as a way of obtaining error-correcting codes with good list-decoding algorithms from error-correcting codes having weak unique-decoding algorithms. To get codes with good rate and efficient list decoding algorithms one needs ... more >>> TR02-024 | 24th April 2002 Piotr Indyk #### List-decoding in Linear Time Spielman showed that one can construct error-correcting codes capable of correcting a constant fraction$\delta << 1/2$of errors, and that are encodable/decodable in linear time. Guruswami and Sudan showed that it is possible to correct more than$50\%$of errors (and thus exceed the half of the ... more >>> TR12-044 | 22nd April 2012 Swastik Kopparty #### List-Decoding Multiplicity Codes We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching$1$while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>> TR11-020 | 20th December 2010 Yijia Chen, Joerg Flum #### Listings and logics There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that${\rm LFP}_{\rm inv}$, the order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>> TR15-038 | 11th March 2015 Gil Cohen #### Local Correlation Breakers and Applications to Three-Source Extractors and Mergers Revisions: 1 We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of$r$(arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of$r$random variables ... more >>> TR17-138 | 17th September 2017 Srikanth Srinivasan, Madhu Sudan #### Local decoding and testing of polynomials over grids The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that$n$-variate polynomials of total degree at most$d$over grids, i.e. sets of the form$A_1 \times A_2 \times \cdots \times A_n$, form error-correcting codes (of distance at least$2^{-d}$provided$\min_i\{|A_i|\}\geq 2$). In this work we explore their local decodability and local testability. ... more >>> TR16-129 | 16th August 2016 Emanuele Viola, Avi Wigderson #### Local Expanders Revisions: 1 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, Steurer, and Wigderson (2009) ask 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 ... more >>> TR07-108 | 27th October 2007 Moses Charikar, Konstantin Makarychev, Yury Makarychev #### Local Global Tradeoffs in Metric Embeddings Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_1. This is a natural mathematical question and is also motivated by the study of relaxations ... more >>> TR10-047 | 23rd March 2010 Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma #### Local list decoding with a constant number of queries Revisions: 1 Recently Efremenko showed locally-decodable codes of sub-exponential length. That result showed that these codes can handle up to$\frac{1}{3} $fraction of errors. In this paper we show that the same codes can be locally unique-decoded from error rate$\half-\alpha$for any$\alpha>0$and locally list-decoded from error rate$1-\alpha$... more >>> TR17-104 | 13th June 2017 Brett Hemenway, Noga Ron-Zewi, Mary Wootters #### Local List Recovery of High-rate Tensor Codes & Applications In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first {\em capacity-achieving} locally list-decodable ... more >>> TR09-115 | 13th November 2009 Swastik Kopparty, Shubhangi Saraf #### Local list-decoding and testing of random linear codes from high-error In this paper, we give surprisingly efficient algorithms for list-decoding and testing {\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable in the {\em high-error} regime with only a {\em constant} number of queries. More precisely, we show that ... more >>> TR16-163 | 25th October 2016 Matthew Hastings #### Local Maxima and Improved Exact Algorithm for MAX-2-SAT Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima hat an instance of MAX-2-SAT can have. We give upper bounds in both the sparse ... more >>> TR15-128 | 10th August 2015 Roee David, Elazar Goldenberg, Robert Krauthgamer #### Local Reconstruction of Low-Rank Matrices and Subspaces Revisions: 2 We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an$n\times m$matrix$M$over a field$\mathbb{F}$and the goal is to reconstruct a (near-optimal) matrix$M'$that is low-rank and close to$M$under some distance function$\Delta$. Furthermore, the reconstruction must be local, ... more >>> TR13-099 | 6th July 2013 Hamidreza Jahanjou, Eric Miles, Emanuele Viola #### Local reductions Revisions: 3 We reduce non-deterministic time$T \ge 2^n$to a 3SAT instance$\phi$of size$|\phi| = T \cdot \log^{O(1)} T$such that there is an explicit circuit$C$that on input an index$i$of$\log |\phi|$bits outputs the$i$th clause, and each output bit of$C$depends on ... more >>> TR17-126 | 7th August 2017 Swastik Kopparty, Shubhangi Saraf #### Local Testing and Decoding of High-Rate Error-Correcting Codes We survey the state of the art in constructions of locally testable codes, locally decodable codes and locally correctable codes of high rate. more >>> TR16-125 | 31st July 2016 Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu #### Local Testing for Membership in Lattices Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in ... more >>> TR11-158 | 25th November 2011 Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin #### Locality from Circuit Lower Bounds We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>> TR13-098 | 28th June 2013 Benny Applebaum, Yoni Moses #### Locally Computable UOWHF with Linear Shrinkage We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs)$H:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>> TR03-046 | 11th June 2003 Philippe Moser #### Locally Computed Baire's Categories on Small Complexity Classes We strengthen an earlier notion of resource-bounded Baire's categories, and define resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP and on probabilistic complexity classes such as BPP. We give an alternative characterization of meager sets via resource-bounded Banach Mazur games. We show that the class ... more >>> TR04-051 | 10th June 2004 Zdenek Dvorák, Daniel Král, Ondrej Pangrác #### Locally consistent constraint satisfaction problems An instance of a constraint satisfaction problem is$l$-consistent if any$l$constraints of it can be simultaneously satisfied. For a set$\Pi$of constraint types,$\rho_l(\Pi)$denotes the largest ratio of constraints which can be satisfied in any$l$-consistent instance composed by constraints from the set$\Pi$. In the ... more >>> TR14-107 | 10th August 2014 Or Meir #### Locally Correctable and Testable Codes Approaching the Singleton Bound Revisions: 2 Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in ... more >>> TR07-040 | 12th April 2007 Kiran Kedlaya, Sergey Yekhanin #### Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major ... more >>> TR05-044 | 6th April 2005 Zeev Dvir, Amir Shpilka #### Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>> TR13-115 | 27th August 2013 Daniele Micciancio #### Locally Dense Codes The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>> TR03-050 | 16th June 2003 Daniel Král #### Locally satisfiable formulas A CNF formula is k-satisfiable if each k clauses of it can be satisfied simultaneously. Let \pi_k be the largest real number such that for each k-satisfiable formula with variables x_i, there are probabilities p_i with the following property: If each variable x_i is chosen randomly and independently to be ... more >>> TR16-122 | 11th August 2016 Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf #### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate$R$and minimum distance$\delta$of a binary code. The best known tradeoff is the Gilbert-Varshamov bound, and says that for every$\delta \in (0, 1/2)$, there are ... more >>> TR09-128 | 29th November 2009 Gillat Kol, Ran Raz #### Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>> TR13-114 | 24th August 2013 Parikshit Gopalan, Salil Vadhan, Yuan Zhou #### Locally Testable Codes and Cayley Graphs Revisions: 1 We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over$\F_2^h$: \begin{enumerate} \item A locally testable code is equivalent to a Cayley graph over$\F_2^h$whose set of generators is significantly larger than$h$and has no short linear dependencies, but yields a ... more >>> TR02-050 | 5th August 2002 Oded Goldreich, Madhu Sudan #### Locally Testable Codes and PCPs of Almost-Linear Length Locally testable codes are error-correcting codes that admit very efficient codeword tests. Specifically, using a constant number of (random) queries, non-codewords are rejected with probability proportional to their distance from the code. Locally testable codes are believed to be the combinatorial core of PCPs. However, the relation is ... more >>> TR09-126 | 26th November 2009 Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman #### Locally Testable Codes Require Redundant Testers Revisions: 3 Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) {\em many} small weight ... more >>> TR10-130 | 18th August 2010 Tali Kaufman, Michael Viderman #### Locally Testable vs. Locally Decodable Codes Revisions: 1 We study the relation between locally testable and locally decodable codes. Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with ... more >>> TR01-013 | 2nd February 2001 Michal Koucky #### Log-space Constructible Universal Traversal Sequences for Cycles of Length$O(n^{4.03})$The paper presents a simple construction of polynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even$NC^1$) constructible and are of length$O(n^{4.03})$. Our result improves the previously known upper-bound$O(n^{4.76})$for log-space constructible universal traversal sequences for cycles. more >>> TR07-091 | 10th September 2007 Martin Grohe #### Logic, Graphs, and Algorithms Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic ... more >>> TR16-154 | 21st September 2016 Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor #### Logical Induction We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running ... more >>> TR01-088 | 29th October 2001 Alexander Shen, Nikolay Vereshchagin #### Logical operations and Kolmogorov complexity We define Kolmogorov complexity of a set of strings as the minimal Kolmogorov complexity of its element. Consider three logical operations on sets going back to Kolmogorov and Kleene: (A OR B) is the direct sum of A,B, (A AND B) is the cartesian product of A,B, more >>> TR01-089 | 29th October 2001 Andrej Muchnik, Nikolay Vereshchagin #### Logical operations and Kolmogorov complexity. II We invistigate what is the minimal length of a program mapping A to B and at the same time mapping C to D (where A,B,C,D are binary strings). We prove that it cannot be expressed in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C), ..., their ... more >>> TR03-077 | 4th September 2003 Till Tantau #### Logspace Optimisation Problems and their Approximation Properties This paper introduces logspace optimisation problems as analogues of the well-studied polynomial-time optimisation problems. Similarly to them, logspace optimisation problems can have vastly different approximation properties, even though the underlying existence and budget problems have the same computational complexity. Numerous natural problems are presented that exhibit such a varying ... more >>> TR09-050 | 28th May 2009 Jan Kyncl, Tomas Vyskocil #### Logspace reduction of directed reachability for bounded genus graphs to the planar case Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s,t, determine whether there is a directed path from s to t in G. Directed reachability is a standard complete problem for the complexity class NL. Planar reachability is an ... more >>> TR10-062 | 7th April 2010 Michael Elberfeld, Andreas Jakoby, Till Tantau #### Logspace Versions of the Theorems of Bodlaender and Courcelle Bodlaender's Theorem states that for every$k$there is a linear-time algorithm that decides whether an input graph has tree width~$k$and, if so, computes a width-$k$tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula$\phi$and for every$k$there is ... more >>> TR96-060 | 19th November 1996 Bernd Borchert, Frank Stephan #### Looking for an Analogue of Rice's Theorem in Complexity Theory Rice's Theorem says that every nontrivial semantic property of programs is undecidable. It this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. more >>> TR07-080 | 7th August 2007 Chris Peikert, Brent Waters #### Lossy Trapdoor Functions and Their Applications We propose a new general primitive called lossy trapdoor functions (lossy TDFs), and realize it under a variety of different number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of standard lattice problems. Using lossy TDFs, we develop a new approach for constructing ... more >>> TR09-127 | 25th November 2009 Brett Hemenway, Rafail Ostrovsky #### Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems Revisions: 2 In STOC '08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure ... more >>> TR17-180 | 26th November 2017 Irit Dinur, Yuval Filmus, Prahladh Harsha #### Low degree almost Boolean functions are sparse juntas Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to$\mu_p$for every *constant*$p$. When$p$is allowed to be very small, new phenomena emerge. ... more >>> TR15-111 | 8th July 2015 Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky #### Low Distortion Embedding from Edit to Hamming Distance using Coupling Revisions: 1 The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings$x,y$lying in the Boolean hypercube. The edit distance between$x$and$y$is defined as the minimum number of character insertion, deletion, and bit flips needed for converting$x$into$y$. ... more >>> TR10-004 | 6th January 2010 Eli Ben-Sasson, Michael Viderman #### Low Rate Is Insufficient for Local Testability Revisions: 3 Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable). Kopparty ... more >>> TR11-095 | 22nd June 2011 Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie #### Low uniform versions of NC1 Revisions: 1 In the setting known as DLOGTIME-uniformity, the fundamental complexity classes$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$have several robust characterizations. In this paper we refine uniformity further and examine the impact of these refinements on$NC^1$and its subclasses. When applied to the logarithmic circuit depth characterization of$NC^1$, some refinements leave ... more >>> TR17-008 | 14th January 2017 Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan #### Low-Complexity Cryptographic Hash Functions Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>> TR06-054 | 16th April 2006 Alex Samorodnitsky #### Low-degree tests at large distances 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. In particular, we show that functions with small ... more >>> TR13-177 | 10th December 2013 Eric Allender, Nikhil Balaji, Samir Datta #### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs Revisions: 1 We present improved uniform TC$^0$circuits for division, matrix powering, and related problems, where the improvement is in terms of majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>> TR06-125 | 20th September 2006 Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto #### Low-Depth Witnesses are Easy to Find Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity We show how to find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard ... more >>> TR07-069 | 29th July 2007 Ronen Shaltiel, Chris Umans #### Low-end uniform hardness vs. randomness tradeoffs for AM In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>> TR16-106 | 15th July 2016 Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma #### Low-error two-source extractors for polynomial min-entropy Revisions: 1 We construct explicit two-source extractors for$n$bit sources, requiring$n^\alpha$min-entropy and having error$2^{-n^\beta}$, for some constants$0 < \alpha,\beta < 1$. Previously, constructions for exponentially small error required either min-entropy$0.49n$\cite{Bou05} or three sources \cite{Li15}. The construction combines somewhere-random condensers based on the Incidence Theorem \cite{Zuc06,Li11}, ... more >>> TR16-084 | 23rd May 2016 Shalev Ben-David #### Low-Sensitivity Functions from Unambiguous Certificates We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>> TR15-139 | 25th August 2015 Eli Ben-Sasson, Gal Maor #### Lower bound for communication complexity with no public randomness We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was first stated in Yao's seminal paper [STOC 1979], but no full proof appears in the literature. Our proof ... more >>> TR16-153 | 28th September 2016 Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah #### Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials Revisions: 3 The power symmetric polynomial on$n$variables of degree$d$is defined as$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by ... more >>> TR12-007 | 28th January 2012 Ruiwen Chen, Valentine Kabanets #### Lower Bounds against Weakly Uniform Circuits Revisions: 1 A family of Boolean circuits$\{C_n\}_{n\geq 0}$is called \emph{$\gamma(n)$-weakly uniform} if there is a polynomial-time algorithm for deciding the direct-connection language of every$C_n$, given \emph{advice} of size$\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one to interpolate between complete uniformity (when$\gamma(n)=0$) ... more >>> TR10-022 | 23rd February 2010 Vitaly Feldman, Homin Lee, Rocco Servedio #### Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas Much work has been done on learning various classes of simple'' monotone functions under the uniform distribution. In this paper we give the first unconditional lower bounds for learning problems of this sort by showing that polynomial-time algorithms cannot learn constant-depth monotone Boolean formulas under the uniform distribution in the ... more >>> TR17-077 | 30th April 2017 Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan #### Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring$\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>> TR08-006 | 18th January 2008 Ran Raz, Amir Yehudayoff #### Lower Bounds and Separations for Constant Depth Multilinear Circuits We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth$d$... more >>> TR98-036 | 11th June 1998 Vince Grolmusz, Gábor Tardos #### Lower Bounds for (MOD p -- MOD m) Circuits Modular gates are known to be immune for the random restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and Hastad. We demonstrate here a random clustering technique which overcomes this difficulty and is capable to prove generalizations of several known modular circuit lower bounds of Barrington, Straubing, Therien; Krause ... more >>> TR16-189 | 21st November 2016 Arnab Bhattacharyya, Sivakanth Gopi #### Lower bounds for 2-query LCCs over large alphabet A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates. We show that any zero-error$2$-query locally correctable code$\mathcal{C}: \{0,1\}^k \to \Sigma^n$that can correct a constant fraction of corrupted symbols must ... more >>> TR16-107 | 17th July 2016 Nathanael Fijalkow #### Lower Bounds for Alternating Online Space Complexity Revisions: 1 The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm, represented by a machine which scans the input exactly once from left to right. In this paper, we study alternating machines as introduced by ... more >>> TR14-026 | 27th February 2014 Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf #### Lower Bounds for Approximate LDCs We study an approximate version of$q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A$q$-query$(\alpha,\delta)$-approximate LDC is a set$V$of$n$points in$\mathbb{R}^d$so that, for each$i \in [d]$there are$\Omega(\delta n)$... more >>> TR17-185 | 28th November 2017 Makrand Sinha #### Lower Bounds for Approximating the Matching Polytope We prove that any extended formulation that approximates the matching polytope on$n$-vertex graphs up to a factor of$(1+\varepsilon)$for any$\frac2n \le \varepsilon \le 1$must have at least${n}\choose{{\alpha}/{\varepsilon}}$defining inequalities where$0<\alpha<1$is an absolute constant. This is tight as exhibited by the$(1+\varepsilon)$approximating linear ... more >>> TR08-032 | 18th March 2008 Dmitriy Cherukhin #### Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates We consider bounded depth circuits over an arbitrary field$K$. If the field$K$is finite, then we allow arbitrary gates$K^n\to K$. For instance, in the case of field$GF(2)$we allow any Boolean gates. If the field$K$is infinite, then we allow only polinomials. For every fixed ... more >>> TR03-004 | 24th December 2002 Eli Ben-Sasson, Prahladh Harsha #### Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games We present a simple proof of the bounded-depth Frege lower bounds of Pitassi et. al. and Krajicek et. al. for the pigeonhole principle. Our method uses the interpretation of proofs as two player games given by Pudlak and Buss. Our lower bound is conceptually simpler than previous ones, and relies ... more >>> TR06-079 | 12th June 2006 Kristoffer Arnsfelt Hansen #### Lower Bounds for Circuits with Few Modular Gates using Exponential Sums We prove that any AC0 circuit augmented with {epsilon log^2 n} MOD_m gates and with a MAJORITY gate at the output, require size n^{Omega(log n)} to compute MOD_l, when l has a prime factor not dividing m and epsilon is sufficiently small. We also obtain ... more >>> TR95-027 | 30th May 1995 Frederic Green #### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate We say an integer polynomial$p$, on Boolean inputs, weakly$m$-represents a Boolean function$f$if$p$is non-constant and is zero (mod$m$), whenever$f$is zero. In this paper we prove that if a polynomial weakly$m$-represents the Mod$_q$function on$n$inputs, where$q$and$m$more >>> TR15-012 | 24th January 2015 Mika Göös #### Lower Bounds for Clique vs. Independent Set We prove an$\omega(\log n)$lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the Alon--Saks--Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity ... more >>> TR15-185 | 24th November 2015 Arnab Bhattacharyya, Sivakanth Gopi #### Lower bounds for constant query affine-invariant LCCs and LTCs Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is ... more >>> TR13-100 | 15th July 2013 Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan #### Lower bounds for depth$4$formulas computing iterated matrix multiplication We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth$4$arithmetic formula computing the product of$d$generic matrices of size$n \times n$, IMM$_{n,d}$, has size$n^{\Omega(\sqrt{d})}$as long as$d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>> TR13-068 | 3rd May 2013 Mrinal Kumar, Shubhangi Saraf #### Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin We study the class of homogenous$\Sigma\Pi\Sigma\Pi(r)$circuits, which are depth 4 homogenous circuits with top fanin bounded by$r$. We show that any homogenous$\Sigma\Pi\Sigma\Pi(r)$circuit computing the permanent of an$n\times n$matrix must have size at least$\exp\left(n^{\Omega(1/r)}\right)$. In a recent result, Gupta, Kamath, Kayal and ... more >>> TR14-089 | 16th July 2014 Neeraj Kayal, Chandan Saha #### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin Revisions: 1 Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field$\mathbb{F}$of characteristic zero. We resolve this problem by proving a$N^{\Omega(\frac{d}{\tau})}$lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>> TR10-120 | 27th July 2010 Noa Eidelstein, Alex Samorodnitsky #### Lower bounds for designs in symmetric spaces A design is a finite set of points in a space on which every "simple" functions averages to its global mean. Illustrative examples of simple functions are low-degree polynomials on the Euclidean sphere or on the Hamming cube. We prove lower bounds on designs in spaces with a large group ... more >>> TR13-116 | 29th August 2013 Albert Atserias, Moritz Müller, Sergi Oliva #### Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle The relativized weak pigeonhole principle states that if at least$2n$out of$n^2$pigeons fly into$n$holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size$2^{(\log n)^{3/2-\epsilon}}$for every$\epsilon > 0$and every sufficiently ... more >>> TR16-165 | 30th October 2016 Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay #### Lower Bounds for Elimination via Weak Regularity We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let$f:\{0,1\}^n \to \{0,1\}$be any boolean function. Alice and Bob get$k$inputs ... more >>> TR07-137 | 6th November 2007 Yijia Chen, Jörg Flum, Moritz Müller #### Lower Bounds for Kernelizations Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a `linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>> TR01-080 | 14th November 2001 Oded Goldreich, Howard Karloff, Leonard J. Schulman, Luca Trevisan #### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval Revisions: 3 We prove that if a linear error correcting code$\C:\{0,1\}^n\to\{0,1\}^m$is such that a bit of the message can be probabilistically reconstructed by looking at two entries of a corrupted codeword, then$m = 2^{\Omega(n)}$. We also present several extensions of this result. We show a reduction from the ... more >>> TR99-019 | 7th June 1999 Detlef Sieling #### Lower Bounds for Linear Transformed OBDDs and FBDDs Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have been suggested as a generalization of OBDDs for the representation and manipulation of Boolean functions. Instead of variables as in the case of OBDDs parities of variables may be tested at the nodes of an LTOBDD. By this extension it is ... more >>> TR03-057 | 21st July 2003 Scott Aaronson #### Lower Bounds for Local Search by Quantum Arguments The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}^n, we show a lower bound of Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to solve this ... more >>> TR05-053 | 4th May 2005 Paul Beame, Nathan Segerlind #### Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>> TR01-060 | 23rd August 2001 Amir Shpilka #### Lower bounds for matrix product We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two$n \times n$matrices over finite fields. In particular we obtain the following results: 1. We show that the number of product gates in any bilinear (or quadratic) ... more >>> TR00-029 | 30th April 2000 Ran Raz, Amir Shpilka #### Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates Revisions: 1 We prove super-linear lower bounds for the number of edges in constant depth circuits with$n$inputs and up to$n$outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits, constant depth threshold circuits ... more >>> TR14-169 | 9th December 2014 Stasys Jukna #### Lower Bounds for Monotone Counting Circuits A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of evaluated to 1 by a given 0-1 input vector (with multiplicities ... more >>> TR97-032 | 11th July 1997 Jan Johannsen #### Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes Using a notion of real communication complexity recently introduced by J. Krajicek, we prove a lower bound on the depth of monotone real circuits and the size of monotone real formulas for st-connectivity. This implies a super-polynomial speed-up of dag-like over tree-like Cutting Planes proofs. more >>> TR95-001 | 1st January 1995 Amos Beimel, Anna Gal, Michael S. Paterson #### Lower Bounds for Monotone Span Programs The model of span programs is a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for contact schemes, symmetric branching programs and for formula size. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for ... more >>> TR07-014 | 23rd January 2007 Amit Chakrabarti #### Lower Bounds for Multi-Player Pointer Jumping We consider the$k$-layer pointer jumping problem in the one-way multi-party number-on-the-forehead communication model. In this problem, the input is a layered directed graph with each vertex having outdegree$1$, shared amongst$k$players: Player~$i$knows all layers {\em except} the$i$th. The players must communicate, in the order$1,2,\ldots,k$, ... more >>> TR12-141 | 22nd October 2012 Dmitry Itsykson, Dmitry Sokolov #### Lower bounds for myopic DPLL algorithms with a cut heuristic The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>> TR04-083 | 8th September 2004 Boaz Barak, Yehuda Lindell, Salil Vadhan #### Lower Bounds for Non-Black-Box Zero Knowledge We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: <ol> <li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>> TR00-042 | 21st June 2000 Lars Engebretsen #### Lower Bounds for non-Boolean Constraint Satisfaction Revisions: 1 We show that the k-CSP problem over a finite Abelian group G cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for any constant epsilon>0, unless P=NP. This lower bound matches well with the best known upper bound, |G|^{k-1}, of Serna, Trevisan and Xhafa. The proof uses a combination of PCP techniques---most notably a ... more >>> TR15-022 | 9th February 2015 Nutan Limaye, Guillaume Malod, Srikanth Srinivasan #### Lower bounds for non-commutative skew circuits Revisions: 1 Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>> TR01-020 | 20th February 2001 N. S. Narayanaswamy, C.E. Veni Madhavan #### Lower Bounds for OBDDs and Nisan's pseudorandom generator We present a new boolean function for which any Ordered Binary Decision Diagram (OBDD) computing it has an exponential number of nodes. This boolean function is obtained from Nisan's pseudorandom generator to derandomize space bounded randomized algorithms. Though the relation between hardness and randomness for computational models is well ... more >>> TR13-083 | 7th June 2013 Miklos Ajtai #### Lower Bounds for RAMs and Quantifier Elimination For each natural number$d$we consider a finite structure${\bf M}_{d}$whose universe is the set of all$0,1$-sequence of length$n=2^{d}$, each representing a natural number in the set$\lbrace 0,1,...,2^{n}-1\rbrace$in binary form. The operations included in the structure are the four constants$0,1,2^{n}-1,n$, multiplication and addition ... more >>> TR15-073 | 25th April 2015 Neeraj Kayal, Chandan Saha #### Lower Bounds for Sums of Products of Low arity Polynomials We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial,$IMM_{d, n}$(corresponding to the product of$d$matrices of size$n \times n$each), any expression of the form more >>> TR02-064 | 14th November 2002 Andrej Bogdanov, Luca Trevisan #### Lower Bounds for Testing Bipartiteness in Dense Graphs We consider the problem of testing bipartiteness in the adjacency matrix model. The best known algorithm, due to Alon and Krivelevich, distinguishes between bipartite graphs and graphs that are$\epsilon$-far from bipartite using$O((1/\epsilon^2)polylog(1/epsilon)$queries. We show that this is optimal for non-adaptive algorithms, up to the ... more >>> TR13-036 | 13th March 2013 Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev #### Lower Bounds for Testing Properties of Functions on Hypergrid Domains Revisions: 1 We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions$ f : [n]^d \rightarrow \mathbb R$on the hypergrid: monotonicity, convexity, and the Lipschitz property. Our lower bounds also apply to the more restricted setting ... more >>> TR09-066 | 13th August 2009 Arnab Bhattacharyya, Ning Xie #### Lower Bounds for Testing Triangle-freeness in Boolean Functions Let$f_{1},f_{2}, f_{3}:\mathbb{F}_{2}^{n} \to \{0,1\}$be three Boolean functions. We say a triple$(x,y,x+y)$is a \emph{triangle} in the function-triple$(f_{1}, f_{2}, f_{3})$if$f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$.$(f_{1}, f_{2}, f_{3})$is said to be \emph{triangle-free} if there is no triangle in the triple. The distance between a function-triple and ... more >>> TR14-150 | 10th November 2014 Justin Thaler #### Lower Bounds for the Approximate Degree of Block-Composed Functions Revisions: 3 We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function$f$on$N$bits, define$F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$to be the function on$M \cdot N$bits obtained by block-composing$f$with a specific DNF known ... more >>> TR14-139 | 31st October 2014 Hong Van Le #### Lower bounds for the circuit size of partially homogeneous polynomials Revisions: 1 In this paper we associate to each multivariate polynomial$f$that is homogeneous relative to a subset of its variables a series of polynomial families$P_\lambda (f)$of$m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in$P_\lambda (f)$is bounded from above ... more >>> TR94-019 | 12th December 1994 #### Lower Bounds for the Computational Power of Networks of Spiking We investigate the computational power of a formal model for networks of spiking neurons. It is shown that simple operations on phase-differences between spike-trains provide a very powerful computational tool that can in principle be used to carry out highly complex computations on a small network of spiking neurons. We ... more >>> TR95-034 | 30th June 1995 Christoph Meinel, Stephan Waack #### Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems We investigate the probabilistic communication complexity (more exactly, the majority communication complexity,) of the graph accessibility problem GAP and its counting versions MOD_k-GAP, k > 1. Due to arguments concerning matrix variation ranks and certain projection reductions, we prove that, for any partition of the input variables, more >>> TR97-042 | 22nd September 1997 Russell Impagliazzo, Pavel Pudlak, Jiri Sgall #### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm Razborov~\cite{Razborov96} recently proved that polynomial calculus proofs of the pigeonhole principle$PHP_n^m$must have degree at least$\ceiling{n/2}+1$over any field. We present a simplified proof of the same result. The main idea of our proof is the same as in the original proof of Razborov: we want to describe ... more >>> TR03-068 | 30th July 2003 Matthias Homeister #### Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs We prove the first lower bound for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. Proving a superpolynomial lower bound for read-once parity branching programs is still a challenging open problem. The following variant ... more >>> TR14-080 | 11th June 2014 Stasys Jukna #### Lower Bounds for Tropical Circuits and Dynamic Programs Revisions: 1 Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>> TR10-085 | 20th May 2010 Eli Ben-Sasson, Jan Johannsen #### Lower bounds for width-restricted clause learning on small width formulas It has been observed empirically that clause learning does not significantly improve the performance of a SAT solver when restricted to learning clauses of small width only. This experience is supported by lower bound theorems. It is shown that lower bounds on the runtime of width-restricted clause learning follow from ... more >>> TR16-050 | 31st March 2016 Roei Tell #### Lower Bounds on Black-Box Reductions of Hitting to Density Estimation Revisions: 1 We consider the following problem. A deterministic algorithm tries to find a string in an unknown set$S\subseteq\{0,1\}^n$that is guaranteed to have large density (e.g.,$|S|\ge2^{n-1}$). However, the only information that the algorithm can obtain about$S$is estimates of the density of$S$in adaptively chosen subsets of ... more >>> TR12-038 | 6th April 2012 Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao #### Lower bounds on information complexity via zero-communication protocols and applications We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition ... more >>> TR12-108 | 4th September 2012 Arkadev Chattopadhyay, Rahul Santhanam #### Lower Bounds on Interactive Compressibility by Constant-Depth Circuits We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class$\C$, and correlation with circuits in$\C$. We use this connection to prove the first lower bounds on general probabilistic multi-round instance compression. We show that there is no probabilistic multi-round ... more >>> TR00-002 | 23rd December 1999 Michael Schmitt #### Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks We calculate lower bounds on the size of sigmoidal neural networks that approximate continuous functions. In particular, we show that for the approximation of polynomials the network size has to grow as$\Omega((\log k)^{1/4})$where$k$is the degree of the polynomials. This bound is ... more >>> TR04-120 | 22nd November 2004 Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis #### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a Alice and Bob want to know if two strings of length$n$are almost equal. That is, do they differ on at most$a$bits? Let$0\le a\le n-1$. We show that any deterministic protocol, as well as any error-free quantum protocol ($C^*$version), for this problem requires at ... more >>> TR00-022 | 2nd May 2000 Rosario Gennaro, Luca Trevisan #### Lower bounds on the efficiency of generic cryptographic constructions We present lower bounds on the efficiency of constructions for Pseudo-Random Generators (PRGs) and Universal One-Way Hash Functions (UOWHFs) based on black-box access to one-way permutations. Our lower bounds are tight as they match the efficiency of known constructions. A PRG (resp. UOWHF) construction based on black-box access is a ... more >>> TR11-016 | 7th February 2011 Sergei Artemenko, Ronen Shaltiel #### Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification Revisions: 1 Hardness amplification results show that for every function$f$there exists a function$Amp(f)$such that the following holds: if every circuit of size$s$computes$f$correctly on at most a$1-\delta$fraction of inputs, then every circuit of size$s'$computes$Amp(f)$correctly on at most a$1/2+\eps$... more >>> TR09-010 | 29th January 2009 Nikos Leonardos, Michael Saks #### Lower bounds on the randomized communication complexity of read-once functions We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... more >>> TR98-015 | 16th January 1998 Valentin E. Brimkov, Stefan S. Dantchev #### Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)$a^Tx=1$,$x \in \{0,1\}^n$with real coefficients, in the framework of the Blum-Shub-Smale real number computational model \cite{BSS}. We obtain a new lower bound$\Omega \left( n\log n\right) \cdot f(1/a_{\min})\$ for the time
complexity ... more >>>

TR15-133 | 12th August 2015
Olaf Beyersdorff, Ilario Bonacina, Leroy Chew

#### Lower bounds: from circuits to QBF proof systems

A general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. Although there are famous examples where a transfer from ideas and techniques from ... more >>>

ISSN 1433-8092 | Imprint