Algebraic codes that achieve list decoding capacity were recently
constructed by a careful ``folding'' of the Reed-Solomon code. The
``low-degree'' nature of this folding operation was crucial to the list
decoding algorithm. We show how such folding schemes conducive to list
decoding arise out of the Artin-Frobenius automorphism at primes ... more >>>

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... more >>>

We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known.

The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>>

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\begin{enumerate}
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... more >>>

We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\begin{itemize}
\item To represent $n$ ternary values $t \in
\zot^n$ in ... more >>>

Learning is a central task in computer science, and there are various
formalisms for capturing the notion. One important model studied in
computational learning theory is the PAC model of Valiant (CACM 1984).
On the other hand, in cryptography the notion of ``learning nothing''
is often modelled by the simulation ... more >>>

We continue the study of {\em robust} tensor codes and expand the
class of base codes that can be used as a starting point for the
construction of locally testable codes via robust two-wise tensor
products. In particular, we show that all unique-neighbor expander
codes and all locally correctable codes, ... more >>>

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained
by setting all *-entries to constants 0 or 1. A system of semi-linear
equations over GF(2) has the form Mx=f(x), where M is a completion of
A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ... more >>>

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>>

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

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... more >>>

Color Coding is an algorithmic technique for deciding efficiently
if a given input graph contains a path of a given length (or
another small subgraph of constant tree-width). Applications of the
method in computational biology motivate the study of similar
algorithms for counting the number of copies of a ... more >>>

It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... more >>>

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

The Gap-Hamming-Distance problem arose in the context of proving space
lower bounds for a number of key problems in the data stream model. In
this problem, Alice and Bob have to decide whether the Hamming distance
between their $n$-bit input strings is large (i.e., at least $n/2 +
\sqrt n$) ... more >>>

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

We study the one-way number-on-the-forhead (NOF) communication
complexity of the k-layer pointer jumping problem. Strong lower
bounds for this problem would have important implications in circuit
complexity. All of our results apply to myopic protocols (where
players see only one layer ahead, but can still ... more >>>

A small-biased distribution of bit sequences is defined as one withstanding $GF(2)$-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, $GF(2^n)$ for $n$ that divides the length of the bit sequence. Indeed, this means that we partition the bits ... more >>>

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.
It states that all sets complete for NP under polynomial-time many-one
reductions are P-isomorphic to each other. From previous research
it has been widely believed that all NP-complete sets are reducible
each other by one-to-one and length-increasing polynomial-time
reductions, but ... more >>>

A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders.

Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>

This paper investigates the existence of inseparable disjoint
pairs of NP languages and related strong hypotheses in
computational complexity. Our main theorem says that, if NP does
not have measure 0 in EXP, then there exist disjoint pairs of NP
languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable.
We also relate ... more >>>

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>

We propose a generalization of the traditional algorithmic space and
time complexities. Using the concept introduced, we derive an
unified proof for the deterministic time and space hierarchy
theorems, now stated in a much more general setting. This opens the
possibility for the unification and generalization of other results
that ... more >>>

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial
ring over a field $\F$, where the $x_i$'s are free noncommuting
formal variables. Given a finite automaton $\A$ with the $x_i$'s as
alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$
obtained by natural operations that we ... more >>>

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>

We present a candidate counterexample to the
easy cylinders conjecture, which was recently suggested
by Manindra Agrawal and Osamu Watanabe (ECCC, TR09-019).
Loosely speaking, the conjecture asserts that any 1-1 function
in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential
size that can each be inverted by some polynomial-size circuit.
more >>>

We show that the reachability problem for directed graphs
that are either K_{3,3}-free or K_5-free
is in unambiguous log-space, UL \cap coUL.
This significantly extends the result of Bourke, Tewari, and Vinodchandran
that the reachability problem for directed planar graphs
is in UL \cap coUL.

Our algorithm decomposes ... more >>>

We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We ... more >>>

We study methods of converting algorithms that distinguish pairs
of distributions with a gap that has an absolute value that is noticeable
into corresponding algorithms in which the gap is always positive.
Our focus is on designing algorithms that, in addition to the tested string,
obtain a ... more >>>

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

For current state-of-the-art satisfiability algorithms based on the
DPLL procedure and clause learning, the two main bottlenecks are the
amounts of time and memory used. Understanding time and memory
consumption, and how they are related to one another, is therefore a
question of considerable practical importance. In the field of ... more >>>

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

We study the problem of polynomial identity testing (PIT) for depth
2 arithmetic circuits over matrix algebra. We show that identity
testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field
F is polynomial time equivalent to identity testing of depth 2
(Pi-Sigma) arithmetic circuits over U_2(F), the ... more >>>

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

We propose a model called priority branching trees (pBT ) for backtracking and dynamic
programming algorithms. Our model generalizes both the priority model of Borodin, Nielson
and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence
spans a wide spectrum of algorithms. After witnessing the ... more >>>

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

Khrapchenko's classical lower bound $n^2$ on the formula size of the
parity function~$f$ can be interpreted as designing a suitable
measure of subrectangles of the combinatorial rectangle
$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we
arrived at the concept of \emph{convex measures}. We prove the
more >>>

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

Motivated by questions in property testing, we search for linear
error-correcting codes that have the ``single local orbit'' property:
i.e., they are specified by a single local
constraint and its translations under the symmetry group of the
code. We show that the dual of every ``sparse'' binary code
whose coordinates
more >>>

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>

We put forth a new computational notion of entropy, which measures the
(in)feasibility of sampling high entropy strings that are consistent
with a given protocol. Specifically, we say that the i'th round of a
protocol (A, B) has _accessible entropy_ at most k, if no
polynomial-time strategy A^* can generate ... more >>>

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

The k-DNF resolution proof systems are a family of systems indexed by
the integer k, where the kth member is restricted to operating with
formulas in disjunctive normal form with all terms of bounded arity k
(k-DNF formulas). This family was introduced in [Krajicek 2001] as an
extension of the ... more >>>

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>

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

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.
The Kolmogorov measures that have been ... more >>>

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees ... more >>>

We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +
n/log^{Omega(q)} ... more >>>

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.
Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ... more >>>

Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a ... more >>>

We introduce the notion of a stable instance for a discrete
optimization problem, and argue that in many practical situations
only sufficiently stable instances are of interest. The question
then arises whether stable instances of NP--hard problems are
easier to solve. In particular, whether there exist algorithms
that solve correctly ... more >>>

We present new deterministic algorithms for several cases of the maximum rank matrix completion
problem (for short matrix completion), i.e. the problem of assigning values to the variables in
a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to
the fundamental problems in computational complexity ... more >>>

The well known dichotomy conjecture of Feder and
Vardi states that for every &#64257;nite family &#915; of constraints CSP(&#915;) is
either polynomially solvable or NP-hard. Bulatov and Jeavons re-
formulated this conjecture in terms of the properties of the algebra
P ol(&#915;), where the latter is ... more >>>

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

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>

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

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ... more >>>

We show several unconditional lower bounds for exponential time classes
against polynomial time classes with advice, including:
\begin{enumerate}
\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$
\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$
\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$
\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$.
This improves the best previously known algorithm by Ajtai, Kumar ... more >>>

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

We prove that for every prime $p$ there exists a $(0,1)$-matrix
$M$ of size $t_p(n,m)\times n$ where
$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every
$m$ columns of $M$ are linearly independent over $\Z_p$, the field
of integers modulo $p$ (and therefore over any field of
characteristic $p$ and over the real ... more >>>

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally.In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes.

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom
generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary
constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a
time. This ... more >>>

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity
extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction
more >>>

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.
1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ... more >>>

Long Code testing is a fundamental problem in the area of property
testing and hardness of approximation.
Long Code is a function of the form $f(x)=x_i$ for some index $i$.
In the Long Code testing, the problem is, given oracle access to a
collection of Boolean functions, to decide whether ... more >>>

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.

This inequality allows us to simplify and strengthen several known ... more >>>

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the
decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ... more >>>

In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias ... more >>>

In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?
Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>>

The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that ... more >>>

Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>>

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

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.
We present a simple proof to show that parity cannot be computed by such circuits.
Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ... more >>>

We consider the problem of testing if a given function
$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial
in $n$ variables, also known as the Reed-Muller testing problem.
Alon et al.~\cite{AKKLR} proposed and analyzed a natural
$2^{d+1}$-query test for this property and showed that it accepts
more >>>

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential
size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential
size: we prove that the size of one ... more >>>

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs ... more >>>

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).
This basic construct underlies “hardness amplification” in cryptography, circuit complexity and
PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent
result by Dinur and ... more >>>

In the present paper we show some new complexity bounds for
the matching problem for special graph classes.
We show that for graphs with a polynomially bounded number
of nice cycles, the decision perfect matching problem is in
$SPL$, it is hard for $FewL$, and the construction ... more >>>

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow (JSL 79), where they defined
propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Krajicek (JSL 07) have ... more >>>

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width
are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}.
We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the ... more >>>

We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based
upon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem ... more >>>

The main objective of this survey is to present the important theoretical and experimental results contributed till date in the area of online algorithms for the self organizing sequential search problem, also popularly known as the List Update Problem(LUP) in a chronological way. The survey includes competitiveness results of deterministic ... more >>>

The threshold degree of a Boolean function
$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real
polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We
construct two halfspaces on $\{0,1\}^n$ whose intersection has
threshold degree $\Theta(\sqrt n),$ an exponential improvement on
previous lower bounds. This solves an open problem due to Klivans
(2002) and ... more >>>

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

In the context of proving lower bounds on proof space in $k$-DNF
resolution, [Ben-Sasson and Nordstr&ouml;m 2009] introduced the concept of
minimally unsatisfiable sets of $k$-DNF formulas and proved that a
minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most
$O((mk)^{k+1})$ variables. They also gave an example of ... more >>>

Polynomial identity testing (PIT) is the problem of checking whether a given
arithmetic circuit is the zero circuit. PIT ranks as one of the most important
open problems in the intersection of algebra and computational complexity. In the last
few years, there has been an impressive progress on this ... more >>>

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

The rigidity of a matrix A for target rank r is the minimum number of entries
of A that must be changed to ensure that the rank of the altered matrix is at
most r. Since its introduction by Valiant (1977), rigidity and similar
rank-robustness functions of matrices have found ... more >>>

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two ... more >>>

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

Model theory is a branch of mathematical logic that investigates the
logical properties of mathematical structures. It has been quite
successfully applied to computational complexity resulting in an
area of research called descriptive complexity theory. Descriptive
complexity is essentially a syntactical characterization of
complexity classes using logical formalisms. However, there ... more >>>

Consider a communication network represented by a directed graph $G=(V,E)$ of $n$ nodes and $m$ edges. Assume that edges in $E$ are
partitioned into two sets: a set $C$ of edges with a fixed
non-negative real cost, and a set $P$ of edges whose \emph{price} should instead be set by ... more >>>

We study the power of non-uniform attacks against one-way
functions and pseudorandom generators.

Fiat and Naor show that for every function
$f: [N]\to [N]$
there is an algorithm that inverts $f$ everywhere using
(ignoring lower order factors)
time, space and advice at most $N^{3/4}$.

We show that ... more >>>

Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.

Our main results are:

\begin{itemize}
\item There are explicit $AC^0$ circuits of ... more >>>

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

We give the first sub-exponential time deterministic polynomial
identity testing algorithm for depth-$4$ multilinear circuits with
a small top fan-in. More accurately, our algorithm works for
depth-$4$ circuits with a plus gate at the top (also known as
$\Spsp$ circuits) and has a running time of
$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ... more >>>

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>

We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power of this model.
Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We ... more >>>

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis.

We present a one-pass randomized streaming ... more >>>

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not
be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of
such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.
Canetti et ... more >>>

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of
any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at
least a fraction of $1 - o(1)$ of the transformations in the set.
Albeit the tradeoff between ... more >>>

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question.
We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ... more >>>

In this paper we will be concerned with a large class of packing
and covering problems which includes Vertex Cover and Independent Set.
Typically, for NP-hard problems among them, one can write an LP relaxation and
then round the solution. For instance, for Vertex Cover, one can obtain a
more >>>

In this paper we demonstrate a close connection between UniqueGames and
MultiCut.
%
In MultiCut, one is given a ``network graph'' and a ``demand
graph'' on the same vertex set and the goal is to remove as few
edges from the network graph as ... more >>>

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

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

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

We study the question of whether the value of mathematical programs such as
linear and semidefinite programming hierarchies on a graph $G$, is preserved
when taking a small random subgraph $G'$ of $G$. We show that the value of the
Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is
more >>>

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>

We show that if $\mathcal C$ is a class of graphs which is
"nowhere dense" then first-order model-checking is
fixed-parameter tractable on $\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ... more >>>

Perfect zero-knowledge (PZK) proofs have been constructed in various settings and they are
also interesting from a complexity theoretic perspective. Yet, virtually nothing is known about them. This is in contrast to statistical zero-knowledge proofs, where many general results have been proved using an array of tools, none of which ... more >>>

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:
(1) Constant degree dimension expanders in finite ... more >>>

Let $f$ be a univariate polynomial with real coefficients, $f\in\RR[X]$. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of $f$ in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation.
more >>>

We study the space required by Polynomial Calculus refutations of random $k$-CNFs. We are interested in how many monomials one needs to keep in memory to carry on a refutation. More precisely we show that for $k \geq 4$ a refutation of a random $k$-CNF of $\Delta n$ clauses and ... more >>>

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy,
$\mathbf{PH}$,
is contained in the class $\mathbf{P}^{\#\mathbf{P}}$,
namely the class of languages that can be
decided by a Turing machine in polynomial time given access to an
oracle with the power to compute a function in the ... more >>>

We prove the existence of a $poly(n,m)$-time computable
pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables
and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.
Previously, the best pseudorandom generator for depth-2 circuits had seed
length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$

In this paper we study the possibility of proving the existence of
one-way functions based on average case hardness. It is well-known
that if there exists a polynomial-time sampler that outputs
instance-solution pairs such that the distribution on the instances
is hard on average, then one-way functions exist. We study ... more >>>

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly
chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$
formed by the intersection of $k$ halfspaces, we prove that
$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ... more >>>

We study the complexity of {\em rationalizing} network formation. In
this problem we fix an underlying model describing how selfish
parties (the vertices) produce a graph by making individual
decisions to form or not form incident edges. The model is equipped
with a notion of stability (or equilibrium), and we ... more >>>

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a
structural component, that is they are results of the form:
"every computational problem that can be formalised in a given logic L ... more >>>