A basic fact in linear algebra is that the image of the curve
$f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any
$m-1$ dimensional affine subspace of $C^m$. In other words, the image
of $f$ is not contained in the image of any polynomial-mapping
$G:C^{m-1} ---> C^m$ ... more >>>

We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>

We show that disjointness requires randomized communication
Omega(\frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}})
in the general k-party number-on-the-forehead model of complexity.
The previous best lower bound was Omega(\frac{log n}{k-1}). By
results of Beame, Pitassi, and Segerlind, this implies
2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver
proof systems needed to refute certain unsatisfiable ... more >>>

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a
set $S \subseteq \F^n$, where $\F$ is a finite field, such that
any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be
efficiently interpolated from its values on $S$, even if an
adversary corrupts a constant fraction of the values. ... more >>>

Any proof of P!=NP will have to overcome two barriers: relativization
and natural proofs. Yet over the last decade, we have seen circuit
lower bounds (for example, that PP does not have linear-size circuits)
that overcome both barriers simultaneously. So the question arises of
whether there ... more >>>

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

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

We study the approximability of predicates on $k$ variables from a
domain $[q]$, and give a new sufficient condition for such predicates
to be approximation resistant under the Unique Games Conjecture.
Specifically, we show that a predicate $P$ is approximation resistant
if there exists a balanced pairwise independent distribution over
more >>>

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>

In a two player game, a referee asks two cooperating players (who are
not allowed to communicate) questions sampled from some distribution
and decides whether they win or not based on some predicate of the
questions and their answers. The parallel repetition of the game is
the game in which ... more >>>

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)).

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... more >>>

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries
is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0
for all i,j. We obtain the first exponential lower bound on the
sign-rank of a function in AC^0. Namely, let
f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).
We show that the matrix [f(x,y)]_{x,y} has ... more >>>

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

The parallel repetition theorem states that for any two-prover game,
with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of
the game repeated in parallel $n$ times is at most
$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length
(of the original game) and $c$ is a universal ... more >>>

In this note we consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates.

We define the entropy of an operator f:{0,1}^n --> {0,1}^m is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every ... more >>>

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

Given a set of observed economic choices, can one infer
preferences and/or utility functions for the players that are
consistent with the data? Questions of this type are called {\em
rationalization} or {\em revealed preference} problems in the
economic literature, and are the subject of a rich body of work.

We show that hard sets S for NP must have exponential density, i.e. |S_=n| &#8805; 2^{n^&#949;} for some &#949; > 0 and infinitely many n, unless coNP &#8838; NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n^1-&#949; queries.

In addition we study the instance ... more >>>

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for
multiplying two $N$-bit integers that improves the $O(N\cdot \log
N\cdot \log\log N)$ algorithm by
Sch\"{o}nhage-Strassen. Both these algorithms use modular
arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log
N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over
complex numbers as opposed to ... more >>>

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

Using ideas from automata theory we design a new efficient
(deterministic) identity test for the \emph{noncommutative}
polynomial identity testing problem (first introduced and studied by
Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,
given as input a noncommutative
circuit $C(x_1,\cdots,x_n)$ computing a ... more >>>

Most state-of-the-art satisfiability algorithms today are variants of
the DPLL procedure augmented with clause learning. The main bottleneck
for such algorithms, other than the obvious one of time, is the amount
of memory used. In the field of proof complexity, the resources of
time and memory correspond to the length ... more >>>

The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets:

1. E = UE if, and only ... more >>>

In a seminal paper from 1985, Sistla and Clarke showed
that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete
or PSPACE-complete, depending on the set of temporal operators used.
If, in contrast, the set of propositional operators is restricted, the complexity may decrease.
... more >>>

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

An aperiodic tile set was first constructed by R.Berger while
proving the undecidability of the domino problem. It turned out
that aperiodic tile sets appear in many topics ranging from
logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The
flexibility of this ... more >>>

This paper explores the impact of geometry on computability =
and complexity in
Winfree's model of nanoscale self-assembly. We work in the =
two-dimensional
tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =
first
main theorem says that there is a roughly quadratic function f ... more >>>

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

A basic goal in Property Testing is to identify a
minimal set of features that make a property testable.
For the case when the property to be tested is membership
in a binary linear error-correcting code, Alon et al.~\cite{AKKLR}
had conjectured that the presence of a {\em single} low weight
more >>>

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>>

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... more >>>

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

In this paper we consider two refined questions regarding
the query complexity of testing graph properties
in the adjacency matrix model.
The first question refers to the relation between adaptive
and non-adaptive testers, whereas the second question refers to
testability within complexity that
is inversely proportional to ... more >>>

For a permutation group $G$ acting on the set $\Omega$
we say that two strings $x,y\,:\,\Omega\to\boole$
are {\em $G$-isomorphic} if they are equivalent under
the action of $G$, \ie, if for some $\pi\in G$ we have
$x(i^{\pi})=y(i)$ for all $i\in\Omega$.
Cyclic Shift, Graph Isomorphism ... more >>>

We initiate a systematic study of a special type of property testers.
These testers consist of repeating a basic test
for a number of times that depends on the proximity parameters,
whereas the basic test is oblivious of the proximity parameter.
We refer to such basic ... more >>>

An algebraic source is a random variable distributed
uniformly over the set of common zeros of one or more multivariate
polynomials defined over a finite field $F$. Our main result is
the construction of an explicit deterministic extractor for
algebraic sources over exponentially large prime fields. More
precisely, we give ... more >>>

In this work we relate the deterministic
complexity of factoring polynomials (over
finite
fields) to certain combinatorial objects we
call
m-schemes. We extend the known conditional
deterministic subexponential time polynomial
factoring algorithm for finite fields to get an
underlying m-scheme. We demonstrate ... more >>>

Following the approach of Hemaspaandra and Vollmer, we can define
counting complexity classes #.C for any complexity class C of decision
problems. In particular, the classes #.Pi_{k}P with k >= 1
corresponding to all levels of the polynomial hierarchy have thus been
studied. However, for a large variety of counting ... more >>>

A theorem of Green, Tao, and Ziegler can be stated (roughly)
as follows: if R is a pseudorandom set, and D is a dense subset of R,
then D may
be modeled by a set M that is dense in the entire domain such that D and
more >>>

We exhibit a new computational-based definition of awareness,
informally that our level of unawareness of an object is the amount
of time needed to generate that object within a certain environment.
We give several examples to show this notion matches our intuition
in scenarios where one organizes, accesses and transfers
more >>>

Following up on the work of Megiddo and Vazirani \cite{MV.2007}, who
determined continuity properties of equilibrium prices and
allocations for perhaps the simplest market model, Fisher's linear
case, we do the same for:
\begin{itemize}
\item
Fisher's model with piecewise-linear, concave utilities
\item
Fisher's model with spending constraint utilities
\item
Arrow-Debreu's ... more >>>

Functions in arithmetic NC1 are known to have equivalent constant
width polynomial degree circuits, but the converse containment is
unknown. In a partial answer to this question, we show that syntactic
multilinear circuits of constant width and polynomial degree can be
depth-reduced, though the resulting circuits need not be ... more >>>

We give a randomized polynomial-time identity test for
noncommutative circuits of polynomial degree based on the isolation
lemma. Using this result, we show that derandomizing the isolation
lemma implies noncommutative circuit size lower bounds. More
precisely, we consider two restricted versions of the isolation
lemma and show that derandomizing each ... more >>>

We develop new tools to study the relative complexities of secure
multi-party computation tasks (functionalities) in the Universal
Composition framework. When one task can be securely realized using
another task as a black-box, we interpret this as a
qualitative, complexity-theoretic reduction between the two tasks.
Virtually all previous characterizations of ... more >>>

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

The \emph{Orbit problem} is defined as follows: Given a matrix $A\in
\Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a
non-negative integer $i$ such that $A^i\x=\y$. This problem was
shown to be in deterministic polynomial time by Kannan and Lipton in
\cite{KL1986}. In this paper we place ... more >>>

Higman showed that if A is *any* language then SUBSEQ(A)
is regular, where SUBSEQ(A) is the language of all
subsequences of strings in A. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... more >>>

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow?s Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding ... more >>>

Integer multiplication as one of the basic arithmetic functions has been
in the focus of several complexity theoretical investigations.
Ordered binary decision diagrams (OBDDs) are one of the most common
dynamic data structures for boolean functions.
Among the many areas of application are verification, model checking,
computer-aided design, relational algebra, ... more >>>

Representations of Boolean functions by real polynomials
play an important role in complexity theory. Typically,
one is interested in the least degree of a polynomial
p(x_1,...,x_n) that approximates or sign-represents
a given Boolean function f(x_1,...,x_n). This article
surveys a new and growing body of work in communication
complexity that centers ... more >>>

A merger is a probabilistic procedure which extracts the
randomness out of any (arbitrarily correlated) set of random
variables, as long as one of them is uniform. Our main result is
an efficient, simple, optimal (to constant factors) merger, which,
for $k$ random vairables on $n$ bits each, uses a ... more >>>

We develop quantum fingerprinting technique for constructing quantum
branching programs (QBPs), which are considered as circuits with an
ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered
binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean
functions. The construction of our technique also ... more >>>

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.

This also improves the largest known gap for planar graphs ... more >>>

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

We show that proving exponential lower bounds on depth four arithmetic
circuits imply exponential lower bounds for unrestricted depth arithmetic
circuits. In other words, for exponential sized circuits additional depth
beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

We show analogues of a theorem due to Valiant and Vazirani
for intractable parameterized complexity classes such as W[P], W[SAT]
and the classes of the W-hierarchy as well as those of the A-hierarchy.
We do so by proving a general ``logical'' version of it which may be of
independent interest

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>

The domination number of a graph $G=(V,E)$ is the minimum size of
a dominating set $U \subseteq V$, which satisfies that every
vertex in $V \setminus U$ is adjacent to at least one vertex in
$U$. The notion of a problem kernel refers to a polynomial time
algorithm that achieves ... more >>>

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

We study the question whether the number of rounds in public-coin perfect zero-knowledge (PZK) proofs can be collapsed to a constant. Despite extensive research into the round complexity of interactive
and zero-knowledge protocols, there is no indication how to address this question. Furthermore, the main tool to tackle this question ... more >>>

Locally Decodable Codes (LDC) allow one to decode any particular
symbol of the input message by making a constant number of queries
to a codeword, even if a constant fraction of the codeword is
damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a
$3$-query LDC with sub-exponential length of size
$\exp(\exp(O(\frac{\log ... more >>>

We show that the NP-Complete language 3Sat has a PCP
verifier that makes two queries to a proof of almost-linear size
and achieves sub-constant probability of error $o(1)$. The
verifier performs only projection tests, meaning that the answer
to the first query determines at most one accepting answer to the
more >>>

A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>>

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>>

We give a polynomial time algorithm that computes a
decomposition of a finite group G given in the form of its
multiplication table. That is, given G, the algorithm outputs two
subgroups A and B of G such that G is the direct product
of A ... more >>>

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice.
In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages?
Depending on the complexity of the ... more >>>

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>>

The classical Direct-Product Theorem for circuits says
that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard
to compute on average by small circuits, then the corresponding
$k$-wise direct product function
$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each
$x_i\in\{0,1\}^n$) is significantly harder to compute on average by
slightly smaller ... more >>>

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.
We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to ... more >>>

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas.
The aim of this note is to present a simplified version of his proof.

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>>

We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case.
As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ... more >>>

We consider Generalized Equality, the Hidden Subgroup,
and related problems in the context of quantum Ordered Binary
Decision Diagrams. For the decision versions of considered problems
we show polynomial upper bounds in terms of quantum OBDD width. We
apply a new modification of the fingerprinting technique and present
the algorithms ... more >>>

Motivated by the quantum algorithm in \cite{MN05} for testing
commutativity of black-box groups, we study the following problem:
Given a black-box finite ring $R=\angle{r_1,\cdots,r_k}$ where
$\{r_1,r_2,\cdots,r_k\}$ is an additive generating set for $R$ and a
multilinear polynomial $f(x_1,\cdots,x_m)$ over $R$ also accessed as
a ... more >>>

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>

We consider the task of testing properties of Boolean functions that
are invariant under linear transformations of the Boolean cube. Previous
work in property testing, including the linearity test and the test
for Reed-Muller codes, has mostly focused on such tasks for linear
properties. The one exception is a test ... more >>>

Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec-
tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With
a view to developing the mathematical basics of such a theory, we start with a very simple model
more >>>

We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the ... more >>>

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>>

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

Referring to the query complexity of property testing,
we prove the existence of a rich hierarchy of corresponding
complexity classes. That is, for any relevant function $q$,
we prove the existence of properties that have testing
complexity Theta(q).
Such results are proven in three standard
domains often considered in property ... more >>>

A hypergraph dictatorship test is first introduced by Samorodnitsky
and Trevisan and serves as a key component in
their unique games based $\PCP$ construction. Such a test has oracle
access to a collection of functions and determines whether all the
functions are the same dictatorship, or all their low degree ... more >>>

In this paper we develop techniques that eliminate the need of the Generalized
Riemann Hypothesis (GRH) from various (almost all) known results about deterministic
polynomial factoring over finite fields. Our main result shows that given a
polynomial f(x) of degree n over a finite field k, we ... more >>>

We construct public-key cryptosystems that are secure assuming the
\emph{worst-case} hardness of approximating the length of a shortest
nonzero vector in an $n$-dimensional lattice to within a small
$\poly(n)$ factor. Prior cryptosystems with worst-case connections
were based either on the shortest vector problem for a \emph{special
class} of lattices ... more >>>

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

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(N\log N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear ... more >>>

We show that every high-entropy distribution is indistinguishable from an
efficiently samplable distribution of the same entropy. Specifically, we prove
that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,
then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most
$S\cdot ... more >>>

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these
problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ... more >>>

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

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... more >>>

We investigate the connection between optimal propositional
proof systems and complete languages for promise classes.
We prove that an optimal propositional proof system exists
if and only if there exists a propositional proof system
in which every promise class with the test set in co-NP
... more >>>

We show that the rank of a depth-3 circuit (over any field) that is simple,
minimal and zero is at most O(k^3\log d). The previous best rank bound known was
2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).
This almost resolves the rank question first posed by ... more >>>

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

One way to quantify how dense a multidag is in long paths is to find
the largest n, m such that whichever &le; n edges are removed, there is still
a path from an original input to an original output with &ge; m edges
- the larger ... more >>>

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>