We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

We present an efficient reduction mapping undirected graphs
G with n = 2^k vertices for integers k
to tables of partially specified Boolean functions
g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m,
G has a vertex colouring using m colours if and only if g ... more >>>

Graphical games have been proposed as a game-theoretic model of large-scale
distributed networks of non-cooperative agents. When the number of players is
large, and the underlying graph has low degree, they provide a concise way to
represent the players' payoffs. It has recently been shown that the problem of
finding ... more >>>

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.

In the buy-at-bulk $k$-Steiner tree (or rent-or-buy
$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set
of terminals $T\subseteq V$ including a particular vertex $s$ called
the root, and an integer $k\leq |T|$. There are two cost functions
on the edges of $G$, a buy cost $b:E\longrightarrow ... more >>>

We consider the non-uniform multicommodity buy-at-bulk network
design problem. In this problem we are given a graph $G(V,E)$ with
two cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$ and a rent cost
$r:E\longrightarrow\RR^+$, and a set of source-sink pairs $s_i,t_i\in V$ ($1\leq i\leq \alpha$)
with each pair $i$ ... more >>>

We re-examine the complexity of evaluating monotone planar circuits
MPCVP, with special attention to circuits with cylindrical
embeddings. MPCVP is known to be in NC^3, and for the special
case of upward stratified circuits, it is known to be in
LogDCFL. We characterize cylindricality, which ... more >>>

In this paper we consider the p-ary transitive reduction (TR_p) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. ... more >>>

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.

It is known that finding a Nash equilibrium for win-lose bimatrix
games, i.e., two-player games where the players' payoffs are zero
and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash
equilibrium for win-lose bimatrix games where the number of winning
positions ... more >>>

In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science,
probabilistic algorithms are sometimes simpler and more efficient
than the best known ... more >>>

We formulate a formal syntax of approximate formulas for the logic with counting
quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the
following facts:
$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can
describe {\bf NP}--complete problems and fragments of it capture classes like
{\bf P} ... more >>>

Barnette's conjecture is the statement that every 3-connected cubic
planar bipartite graph is Hamiltonian. Goodey showed that the conjecture
holds when all faces of the graph have either 4 or 6 sides. We
generalize Goodey's result by showing that when the faces of such a
graph are 3-colored, with adjacent ... more >>>

The $H$-matching problem asks to partition the vertices of an input graph $G$
into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$
isomorphic to $H$. The $H$-matching problem has been classified as polynomial
or NP-complete depending on whether $k\leq 2$ or not. We consider a variant
more >>>

A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer $n>0$, let $S_{n}$ be the family of al permutations on $[1,n]=\{1,2,\ldots, n\}$.
For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we ... more >>>

Valiant has proposed a new theory of algorithmic
computation based on perfect matchings and the Pfaffian.
We study the properties of {\it matchgates}---the basic
building blocks in this new theory. We give a set of
algebraic identities
which completely characterize these objects in terms of
the ... more >>>

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)
proved that for
2-dimensional Orthogonal Rectangle
Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar
approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety
more >>>

We present three new quantum hardcore functions for any quantum one-way function. We also give a "quantum" solution to Damgard's question (CRYPTO'88) on his pseudorandom generator by proving the quantum hardcore property of his generator, which has been unknown to have the classical hardcore property.
Our technical tool is ... more >>>

Attempts at classifying computational problems as polynomial time
solvable, NP-complete, or belonging to a higher level in the polynomial
hierarchy, face the difficulty of undecidability. These classes, including
NP, admit a logic formulation. By suitably restricting the formulation, one
finds the logic class MMSNP, or monotone monadic strict NP without
more >>>

We initiate the study of the compressibility of NP problems. We
consider NP problems that have long instances but relatively
short witnesses. The question is, can one efficiently compress an
instance and store a shorter representation that maintains the
information of whether the original input is in the language or
more >>>

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>>

The class TFNP, defined by Megiddo and Papadimitriou, consists of
multivalued functions with values that are polynomially verifiable
and guaranteed to exist. Do we have evidence that such functions are
hard, for example, if TFNP is computable in polynomial-time does
this imply the polynomial-time hierarchy collapses?

We give a relativized ... more >>>

Let $p(x_1,...,x_n) = p(X) , X \in R^{n}$ be a homogeneous polynomial of degree $n$ in $n$ real variables ,
$e = (1,1,..,1) \in R^n$ be a vector of all ones . Such polynomial $p$ is
called $e$-hyperbolic if for all real vectors $X \in R^{n}$ the univariate polynomial
equation ... more >>>

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

We investigate the following lower bound methods for regular
languages: The fooling set technique, the extended fooling set
technique, and the biclique edge cover technique. It is shown that
the maximal attainable lower bound for each of the above mentioned
techniques can be algorithmically deduced from ... more >>>

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

We study the structure of EG[2], the class of Eisenberg-Gale markets
with two agents. We prove that all markets in this class are rational and they
admit strongly polynomial algorithms whenever
the polytope containing the set of feasible utilities of the two agents can be described
via a combinatorial LP. ... more >>>

In our problem we are given a set of customers, their positions on the
plane and their demands. Geometrically, directional antenna with
parameters $\alpha,\rho,R$ is a set
of points with radial coordinates $(\theta,r)$ such that
$\alpha \le \theta \le \alpha+\rho$ and $r \le R$. Given a set of
possible directional ... more >>>

We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange ... more >>>

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

A natural algorithmic scheme in online game playing is called `follow-the-leader', first proposed by Hannan in the 1950's. Simply stated, this method advocates the use of past history to make future predictions, by using the optimal strategy so far as the strategy for the next game iteration. Randomized variations on ... more >>>

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

The reachability problem for graphs cannot be described, in the
sense of descriptive complexity theory, using a single first-order
formula. This is true both for directed and undirected graphs, both
in the finite and infinite. However, if we restrict ourselves to
graphs in which a certain graph parameter is fixed ... more >>>

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives ... more >>>

Under the assumption that NP does not have p-measure 0, we
investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive
reductions: there is a problem that is Turing-complete for NP but
not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

We study the problem of assigning different communication channels to
acces points in a wireless Local Area Network. Each access point will
be assigned a specific radio frequency channel. Since channels with
similar frequencies interfere, it is desirable to assign far apart
channels (frequencies) to nearby access points. Our goal ... more >>>

We consider the problem of finding a $k$-vertex ($k$-edge)
connected spanning subgraph $K$ of a given $n$-vertex graph $G$
while minimizing the maximum degree $d$ in $K$. We give a
polynomial time algorithm for fixed $k$ that achieves an $O(\log
n)$-approximation. The only known previous polynomial algorithms
achieved degree $d+1$ ... more >>>

We prove that any real matrix $A$ contains a subset of at most
$4k/\eps + 2k \log(k+1)$ rows whose span ``contains" a matrix of
rank at most $k$ with error only $(1+\eps)$ times the error of the
best rank-$k$ approximation of $A$. This leads to an algorithm to
find such ... more >>>

Let $\phi$ be a 3CNF formula with n variables and m clauses. A
simple nonconstructive argument shows that when m is
sufficiently large compared to n, most 3CNF formulas are not
satisfiable. It is an open question whether there is an efficient
refutation algorithm that for most such formulas proves ... more >>>

We present a deterministic algorithm producing the number of
$k$-colourings of a graph on $n$ vertices in time
$2^nn^{O(1)}$.
We also show that the chromatic number can be found by a
polynomial space algorithm running in time $O(2.2461^n)$.
Finally, we present a family of ... more >>>

Given a set of monomials, the Minimum AND-Circuit problem asks for a
circuit that computes these monomials using AND-gates of fan-in two and
being of minimum size. We prove that the problem is not polynomial time
approximable within a factor of less than 1.0051 unless P = NP, even if
more >>>

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

We define a new discrete version of scaled dimension and we find
connections between the scaled dimension of a string and its Kolmogorov
complexity and predictability. We give a new characterization
of constructive scaled dimension by Kolmogorov complexity, and prove
a new result about scaled dimension and prediction.

We establish a 1-1 correspondence between Valiant's
character theory of matchgate/matchcircuit
and his signature theory of planar-matchgate/matchgrid,
thus unifying the two theories in expressibility.
Previously we had established a complete characterization
of general matchgates, in terms of a set of
useful Grassmann-Pl{\"u}cker identities.
With this correspondence,
we give a corresponding ... more >>>

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by ... more >>>

A two server private information retrieval (PIR) scheme
allows a user U to retrieve the i-th bit of an
n-bit string x replicated between two servers while each
server individually learns no information about i. The main
parameter of interest in a PIR scheme is its communication
complexity, namely the ... more >>>

Diagonalization is a powerful technique in recursion theory and in
computational complexity \cite{For00}. The limits of this technique are
not clear. On the one hand, many people argue that conflicting
relativizations mean a complexity question cannot be resolved using only
diagonalization. On the other hand, it is not clear that ... more >>>

We show that the Closest Vector
Problem with Preprocessing over infty Norm
is NP-hard to approximate to within a factor of $(\log
n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their
reductions are based on norm embeddings. However, ... more >>>

A coloring of a graph is {\it convex} if it
induces a partition of the vertices into connected subgraphs.
Besides being an interesting property from a theoretical point of
view, tests for convexity have applications in various areas
involving large graphs. Our results concern the important subcase
of testing for ... more >>>

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

This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
two results about this question. First, we give a "quantum oracle
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ... more >>>

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist.

We establish several new characterizations of ZK, and use these characterizations to ... more >>>

We give the first representation-independent hardness results for
PAC learning intersections of halfspaces, a central concept class
in computational learning theory. Our hardness results are derived
from two public-key cryptosystems due to Regev, which are based on the
worst-case hardness of well-studied lattice problems. Specifically, we
prove that a polynomial-time ... more >>>

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results:

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

We construct an explicit polynomial $f(x_1,...,x_n)$, with
coefficients in ${0,1}$, such that the size of any syntactically
multilinear arithmetic circuit computing $f$ is at least
$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field.

Learning an unknown halfspace (also called a perceptron) from
labeled examples is one of the classic problems in machine learning.
In the noise-free case, when a halfspace consistent with all the
training examples exists, the problem can be solved in polynomial
time using linear programming. ... more >>>

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani ... more >>>

We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>>

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

Detecting the relevant attributes of an unknown target concept
is an important and well studied problem in algorithmic learning.
Simple greedy strategies have been proposed that seem to perform reasonably
well in practice if a sufficiently large random subset of examples of the target
concept is provided.

Introducing a ... more >>>

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over $\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>>

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space ... more >>>

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>

This paper is motivated by the open question
whether the union of two disjoint NP-complete sets always is
NP-complete. We discover that such unions retain
much of the complexity of their single components. More precisely,
they are complete with respect to more general reducibilities.

We present a brief survey of results on relations between the Kolmogorov
complexity of infinite strings and several measures of information content
(dimensions) known from dimension theory, information theory or fractal
geometry.

Special emphasis is laid on bounds on the complexity of strings in
more >>>

We consider hypotheses about nondeterministic computation that
have been studied in different contexts and shown to have interesting
consequences:

1. The measure hypothesis: NP does not have p-measure 0.

2. The pseudo-NP hypothesis: there is an NP language that can be
distinguished from any DTIME(2^n^epsilon) language by an ... more >>>

We are going to analyze simple search tree algorithms
for Weighted d-Hitting Set. Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) d-Hitting Set.

We survey the theory of average-case complexity, with a
focus on problems in NP.

We consider computationally-efficient incentive-compatible
mechanisms that use the VCG payment scheme, and study how well they
can approximate the social welfare in auction settings. We obtain a
$2$-approximation for multi-unit auctions, and show that this is
best possible, even though from a purely computational perspective
an FPTAS exists. For combinatorial ... more >>>

We show that every language in NP has a *statistical* zero-knowledge
argument system under the (minimal) complexity assumption that
one-way functions exist. In such protocols, even a computationally
unbounded verifier cannot learn anything other than the fact that the
assertion being proven is true, whereas a polynomial-time prover
cannot convince ... more >>>

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

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

NP-complete problems cannot have efficient algorithms unless P = NP. Due to their importance in practice, however, it is useful to improve the known exponential-time algorithms for NP-complete problems. We survey some of the recent results on such improved exponential-time algorithms for the NP-complete problems satisfiability, graph colorability, and the ... more >>>

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

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily ... more >>>

We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.
We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and
we next show how to extend this algorithm so as to ... more >>>

In Descriptive Complexity, there is a vast amount of literature on
decision problems, and their classes such as \textbf{P, NP, L and NL}. ~
However, research on the descriptive complexity of optimisation problems
has been limited. In a previous paper [Man], we characterised
the optimisation versions of \textbf{P} via expressions ... more >>>

We investigate the effect of restricting the mutation operator in
evolutionary algorithms with respect to the runtime behavior.
Considering the Eulerian cycle problem we present runtime bounds on
evolutionary algorithms with a restricted operator that are much
smaller than the best upper bounds for the ... more >>>

Ant Colony Optimization (ACO) has become quite popular in recent
years. In contrast to many successful applications, the theoretical
foundation of this randomized search heuristic is rather weak.
Building up such a theory is demanded to understand how these
heuristics work as well as to ... more >>>

It is well known that unconditionally secure bit commitment is impossible
even in the quantum world. In this paper a weak variant of quantum bit
commitment, introduced independently by Aharonov et al. and Hardy and Kent
is investigated. In this variant, the parties require some nonzero probability
more >>>

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

We show that in the bounded degree model for graph property testing,
adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ... more >>>

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<ul>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ... more >>>

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>>

2-Opt is probably the most basic and widely used local search
heuristic for the TSP. This heuristic achieves amazingly good
results on "real world" Euclidean instances both with respect to
running time and approximation ratio. There are numerous
experimental studies on the performance of 2-Opt. However, the
theoretical knowledge about ... more >>>

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

Interactive hashing, introduced by Naor et al. [NOVY98], plays
an important role in many cryptographic protocols. In particular, it
is a major component in all known constructions of
statistically-hiding commitment schemes and of zero-knowledge
arguments based on general one-way permutations and on one-way
functions. Interactive hashing with respect to a ... more >>>

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

We study semidefinite programming relaxations of Vertex Cover arising from
repeated applications of the LS+ ``lift-and-project'' method of Lovasz and
Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality
gap remains arbitrarily close to 2. Charikar proves an integrality ... more >>>

This paper concerns the possibility of developing a coherent
theory of security when feasibility is associated
with expected probabilistic polynomial-time (expected PPT).
The source of difficulty is that
the known definitions of expected PPT strategies
(i.e., expected PPT interactive machines)
do not support natural results of the ... more >>>

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound
$k$, we want to decide whether the rank of $M$ can be brought down to
below $r$ by changing at most $k$ entries of $M$. This is a decision
version of the well-studied notion of ... more >>>

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume ... more >>>

Combinatorial property testing deals with the following relaxation
of decision problems: Given a fixed property and an input $x$, one
wants to decide whether $x$ satisfies the property or is ``far''
from satisfying it. The main focus of property testing is in
identifying large families of properties that can be ... more >>>

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

We show that a mild derandomization assumption together with the
worst-case hardness of NP implies the average-case hardness of a
language in non-deterministic quasi-polynomial time. Previously such
connections were only known for high classes such as EXP and
PSPACE.

There has been a long line of research trying to explain ... more >>>

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>

In the last decade, the notion of metric embeddings with
small distortion received wide attention in the literature, with
applications in combinatorial optimization, discrete mathematics, functional
analysis and bio-informatics. The notion of embedding is, given two metric
spaces on the same number of points, to find a bijection that minimizes
more >>>

We present two new methods for finding a lowest common ancestor (LCA)
for each pair of vertices of a directed acyclic graph (dag) on
n vertices and m edges.

The first method is a natural approach that solves the all-pairs LCA
problem for the input dag in time O(nm).

The ... more >>>

In this paper
we establish a general algorithmic framework between bin packing
and strip packing, with which we achieve the same asymptotic
bounds by applying bin packing algorithms to strip packing. More
precisely we obtain the following results: (1) Any offline bin
packing algorithm can be applied to strip packing ... more >>>

Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of $n$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log n$. Under the ... more >>>

Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, ... more >>>

We show that for any $\epsilon > 0$, a maximum-weight triangle in an
undirected graph with $n$ vertices and real weights assigned to
vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$,
where $\omega $ is the exponent of fastest matrix multiplication
algorithm. By the currently best bound ... more >>>

We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a ``latent'' partition V_1,...,V_k. Moreover, consider a ``density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible ... more >>>

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

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

We describe a short and easy to analyze construction of
constant-degree expanders. The construction relies on the
replacement-product, which we analyze using an elementary
combinatorial argument. The construction applies the replacement
product (only twice!) to turn the Cayley expanders of \cite{AR},
whose degree is polylog n, into constant degree
expanders.

Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would ... more >>>

In 1984 Levin put forward a suggestion for a theory of {\em average
case complexity}. In this theory a problem, called a {\em
distributional problem}, is defined as a pair consisting of a
decision problem and a probability distribution over the instances.
Introducing adequate notions of simple distributions and average
more >>>

Much progress has been made on decoding algorithms for
error-correcting codes in the last decade. In this article, we give an
introduction to some fundamental results on iterative, message-passing
algorithms for low-density parity check codes. For certain
important stochastic channels, this line of work has enabled getting
very close to ... more >>>

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

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

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

A q-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 q bits of the codeword C(x), even after
some constant fraction of codeword bits has been corrupted.

We give ... more >>>

A number of recent results have constructed randomness extractors
and pseudorandom generators (PRGs) directly from certain
error-correcting codes. The underlying construction in these
results amounts to picking a random index into the codeword and
outputting $m$ consecutive symbols (the codeword is obtained from
the weak random source in the case ... more >>>

The perfect matching problem is known to
be in P, in randomized NC, and it is hard for NL.
Whether the perfect matching problem is in NC is one of
the most prominent open questions in complexity
theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem
more >>>

A monotone planar circuit (MPC) is a Boolean circuit that can be
embedded in a plane, and that has only AND and OR
gates. Yang showed that the one-input-face
monotone planar circuit value problem (MPCVP) is in NC^2, and
Limaye et. al. improved the bound to ... more >>>

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

We study linear programming relaxations of Vertex Cover and Max Cut
arising from repeated applications of the ``lift-and-project''
method of Lovasz and Schrijver starting from the standard linear
programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that
the integrality gap remains at least $2-\epsilon$ after
$\Omega_\epsilon(\log n)$ ... more >>>

The importance of {\em width} as a resource in resolution theorem proving
has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower
bounds on the size of resolution refutations can be proved in a uniform manner by
demonstrating lower bounds on the width ... more >>>

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ ... more >>>

This note points out a gap between two natural formulations of
the concept of a proof of knowledge, and shows that in all
natural cases (e.g., NP-statements) this gap can be closed.
The aforementioned formulations differ by whether they refer to
(all possible) probabilistic or deterministic prover strategies.
Unlike ... more >>>

It had previously been shown that generic cortical microcircuit
models can perform complex real-time computations on continuous
input streams, provided that these computations can be carried out
with a rapidly fading memory. We investigate in this article the
computational capability of such circuits in the ... more >>>

Circuits composed of threshold gates (McCulloch-Pitts neurons, or
perceptrons) are simplified models of neural circuits with the
advantage that they are theoretically more tractable than their
biological counterparts. However, when such threshold circuits are
designed to perform a specific computational task they usually
differ ... more >>>

We give a complexity-theoretic characterization of the class of problems in NP having zero-knowledge argument systems that is symmetric in its treatment of the zero knowledge and the soundness conditions. From this, we deduce that the class of problems in NP intersect coNP having zero-knowledge arguments is closed under complement. ... more >>>

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>

We prove a strong inapproximability result for routing on directed
graphs with low congestion. Given as input a directed graph on $N$
vertices and a set of source-destination pairs that can be connected
via edge-disjoint paths, we prove that it is hard, assuming NP
doesn't have $n^{O(\log\log n)}$ time randomized ... more >>>

In this paper we ask the question whether the extended Frege proof
system EF satisfies a weak version of the deduction theorem. We
prove that if this is the case, then complete disjoint NP-pairs
exist. On the other hand, if EF is an optimal proof system, ... more >>>

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural objective is to find a ranking ... more >>>

We develop the theory of holographic algorithms. We give
characterizations of algebraic varieties of realizable
symmetric generators and recognizers on the basis manifold,
and a polynomial time decision algorithm for the
simultaneous realizability problem.
Using the general machinery we are able to give
unexpected holographic algorithms for
some counting problems, ... more >>>

We investigate the computational complexity of finding an element of
a permutation group~$H\subseteq S_n$ with a minimal distance to a
given~$\pi\in S_n$, for different metrics on~$S_n$. We assume
that~$H$ is given by a set of generators, such that the problem
cannot be solved in polynomial time ... more >>>

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

We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in ... more >>>

Consider a weather forecaster predicting a probability of rain for
the next day. We consider tests that given a finite sequence of
forecast predictions and outcomes will either pass or fail the
forecaster. Sandroni (2003) shows that any test which passes a
forecaster who knows the distribution of nature, can ... more >>>

We consider the envy-free pricing problem, in which we want to compute revenue maximizing prices for a set of products P assuming that each consumer from a set of consumer samples C will buy the product maximizing her personal utility, i.e., the difference between her respective budget and the product's ... more >>>

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated ... more >>>

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

In a seminal paper from 1985, Sistla and Clarke showed
that satisfiability 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 ... more >>>

We consider the problem of amplifying uniform average-case hardness
of languages in $\NP$, where hardness is with respect to $\BPP$
algorithms. We introduce the notion of \emph{monotone}
error-correcting codes, and show that hardness amplification for
$\NP$ is essentially equivalent to constructing efficiently
\emph{locally} encodable and \emph{locally} list-decodable monotone
codes. The ... more >>>

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

We show how to find in Hamiltonian graphs a cycle of length
$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general
result in which we show that if $G$ has maximum degree $d$ and has a
cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices),
then ... more >>>

We explore whether various complexity classes can have linear or
more generally $n^k$-sized circuit families for some fixed $k$. We
show

1) The following are equivalent,
- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k
- P^NP|| is in SIZE(n^k) for some k
- ONP/1 is in ... more >>>

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>>

We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>>

Quantified constraint satisfaction is the generalization of
constraint satisfaction that allows for both universal and existential
quantifiers over constrained variables, instead
of just existential quantifiers.
We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes
a pattern of quantifier alternation ending in exists or the set of all possible
more >>>