Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

REPORTS > 2006:
All reports in year 2006:
TR06-001 | 1st January 2006
Ran Raz, Iddo Tzameret

The Strength of Multilinear Proofs

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

TR06-002 | 4th January 2006
Eyal Kaplan, Moni Naor, Omer Reingold

Derandomized Constructions of k-Wise (Almost) Independent Permutations

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

TR06-003 | 8th January 2006
Joshua Buresh-Oppenheim, Rahul Santhanam

Making Hard Problems Harder

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

TR06-004 | 6th January 2006
Jesper Torp Kristensen, Peter Bro Miltersen

Finding small OBDDs for incompletely specified truth tables is hard

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

TR06-005 | 13th December 2005
Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

Nash Equilibria in Graphical Games on Trees Revisited

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

TR06-006 | 16th December 2005
Alexander Shen

Multisource algorithmic information theory

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.

more >>>

TR06-007 | 23rd November 2005
MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

Approximating Buy-at-Bulk $k$-Steiner trees

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

TR06-008 | 23rd November 2005
MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk

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

TR06-009 | 10th January 2006
Nutan Limaye, Meena Mahajan, Jayalal Sarma

Evaluating Monotone Circuits on Cylinders, Planes and Tori

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

TR06-010 | 1st December 2005
Reka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag

Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs

In this paper we consider the p-ary transitive reduction (TR<sub>p</sub>) 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 >>>

TR06-011 | 2nd January 2006
Yijia Chen, Martin Grohe

An Isomorphism between Subexponential and Parameterized Complexity Theory

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.

more >>>

TR06-012 | 17th January 2006
Bruno Codenotti, Mauro Leoncini, Giovanni Resta

Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

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

TR06-013 | 24th January 2006
Luca Trevisan

Pseudorandomness and Combinatorial Constructions

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

TR06-014 | 20th December 2005
Argimiro Arratia, Carlos E. Ortiz

On a syntactic approximation to logics that capture complexity classes

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

TR06-015 | 1st February 2006
Tomas Feder, Carlos Subi

On Barnette's conjecture

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

TR06-016 | 1st February 2006
Tomas Feder, Carlos Subi

Partition into $k$-vertex subgraphs of $k$-partite graphs

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

TR06-017 | 12th January 2006
Toshiya Itoh

Improved Lower Bounds for Families of $\varepsilon$-Approximate k$-Restricted Min-Wise Independent Permutations

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

TR06-018 | 8th February 2006
Jin-Yi Cai, Vinay Choudhary

On the Theory of Matchgate Computations

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

TR06-019 | 24th November 2005
Janka Chlebíková, Miroslav Chlebik

Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

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

TR06-020 | 10th February 2006
Akinori Kawachi, Tomoyuki Yamakami

Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Revisions: 1

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

TR06-021 | 10th February 2006
Tomas Feder

Constraint satisfaction: a personal perspective

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

TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

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

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

Computing Nash Equilibria: Approximation and Smoothed Complexity

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

TR06-024 | 18th February 2006
Harry Burhman, Lance Fortnow, Michal Koucky, John Rogers, Nikolay Vereshchagin

Inverting onto functions might not be hard

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

TR06-025 | 19th January 2006
Leonid Gurvits

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\\ Sharper Bounds , Simpler Proofs and Algorithmic Applications

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

TR06-026 | 27th February 2006
Ronen Gradwohl, Salil Vadhan, David Zuckerman

Random Selection with an Adversarial Majority

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

TR06-027 | 22nd February 2006
Hermann Gruber, Markus Holzer

Finding Lower Bounds for Nondeterministic State Complexity is Hard

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

TR06-028 | 21st February 2006
Jonathan Katz, Chiu-Yuen Koo

On Expected Constant-Round Protocols for Byzantine Agreement

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

TR06-029 | 21st February 2006
Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

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

TR06-030 | 17th January 2006
Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar

Packing to angles and sectors

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

TR06-031 | 27th February 2006
Li-Sha Huang, Shang-Hua Teng

On the Approximation and Smoothed Complexity of Leontief Market Equilibria

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

TR06-032 | 25th February 2006
Vitaly Feldman

Optimal Hardness Results for Maximizing Agreements with Monomials

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

TR06-033 | 2nd March 2006
Amit Agarwal, Elad Hazan

Efficient Algorithms for Online Game Playing and Universal Portfolio Management

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

TR06-034 | 9th March 2006
Moni Naor, Guy Rothblum

The Complexity of Online Memory Checking

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

TR06-035 | 19th January 2006
Till Tantau

The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

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

TR06-036 | 7th February 2006
Tobias Riege, Jörg Rothe

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

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

TR06-037 | 10th February 2006
Xi Chen, Xiaotie Deng

On the Complexity of 2D Discrete Fixed Point Problem

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

TR06-038 | 10th February 2006
David Doty, Jack H. Lutz, Satyadev Nandakumar

Finite-State Dimension and Real Arithmetic

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

TR06-039 | 28th February 2006
John Hitchcock, A. Pavan

Comparing Reductions to NP-Complete Sets

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

TR06-040 | 6th March 2006
Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

Channel assignment in wireless networks and classification of minimum graph homomorphism

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

TR06-041 | 6th March 2006
Tomas Feder, Rajeev Motwani, An Zhu

k-connected spanning subgraphs of low degree

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

TR06-042 | 16th March 2006
Amit Deshpande, Santosh Vempala

Adaptive Sampling and Fast Low-Rank Matrix Approximation

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

TR06-043 | 22nd March 2006
Eran Ofek, Uriel Feige

Random 3CNF formulas elude the Lovasz theta function

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

TR06-044 | 24th January 2006
Andreas Björklund, Thore Husfeldt

Inclusion-Exclusion Based Algorithms for Graph Colouring

We present a deterministic algorithm producing the number of
$k$-colourings of a graph on $n$ vertices in time
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 >>>

TR06-045 | 13th March 2006
Jan Arpe, Bodo Manthey

Approximability of Minimum AND-Circuits

Revisions: 1

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

TR06-046 | 1st April 2006
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

A Complete Public-Key Cryptosystem

Comments: 1

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

TR06-047 | 11th February 2006
Maria Lopez-Valdes

Scaled Dimension of Individual Strings

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.

more >>>

TR06-048 | 9th April 2006
Jin-Yi Cai, Vinay Choudhary

Some Results on Matchgates and Holographic Algorithms

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

TR06-049 | 9th April 2006
Guy Wolfovitz

The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

Comments: 1

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

TR06-050 | 18th April 2006
Alexander Razborov, Sergey Yekhanin

An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

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

TR06-051 | 8th April 2006
Alan Nash, Russell Impagliazzo, Jeff Remmel

Infinitely-Often Universal Languages and Diagonalization

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

TR06-052 | 15th April 2006
Wenbin Chen, Jiangtao Meng

Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm

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

TR06-053 | 6th April 2006
Eldar Fischer, Orly Yahalom

Testing Convexity Properties of Tree Colorings

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

TR06-054 | 16th April 2006
Alex Samorodnitsky

Low-degree tests at large distances

We define tests of boolean functions which
distinguish between linear (or quadratic) polynomials, and functions
which are very far, in an appropriate sense, from these
polynomials. The tests have optimal or nearly optimal trade-offs
between soundness and the number of queries.

In particular, we show that functions with small ... more >>>

TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

Quantum Versus Classical Proofs and Advice

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

TR06-056 | 27th April 2006
Salil Vadhan

An Unconditional Study of Computational Zero Knowledge

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

TR06-057 | 19th April 2006
Adam Klivans, Alexander A. Sherstov

Cryptographic Hardness Results for Learning Intersections of Halfspaces

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

TR06-058 | 25th April 2006
Alexander Healy

Randomness-Efficient Sampling within NC^1

Revisions: 1

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:

... more >>>

TR06-059 | 3rd May 2006
Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

New Results for Learning Noisy Parities and Halfspaces

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

TR06-060 | 4th May 2006
Ran Raz, Amir Shpilka, Amir Yehudayoff

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

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.

more >>>

TR06-061 | 5th May 2006
Venkatesan Guruswami, Prasad Raghavendra

Hardness of Learning Halfspaces with Noise

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

TR06-062 | 24th April 2006
Subhas Kumar Ghosh

Unique k-SAT is as Hard as k-SAT

Revisions: 1 , Comments: 3

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

TR06-063 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Approximation Algorithm for the Max k-CSP Problem

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

TR06-064 | 1st May 2006
Moses Charikar, Konstantin Makarychev, Yury Makarychev

Note on MAX 2SAT

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

TR06-065 | 24th May 2006
Jan Arpe, Rüdiger Reischuk

When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---

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

TR06-066 | 5th May 2006
Vitaly Feldman

On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions

Revisions: 1

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

TR06-067 | 12th April 2006
Heiner Ackermann, Heiko Röglin, Berthold Vöcking

On the Impact of Combinatorial Structure on Congestion Games

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

TR06-068 | 6th April 2006
Patrick Briest, Piotr Krysta

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

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

TR06-069 | 11th May 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

The Complexity of Unions of Disjoint Sets

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.

more >>>

TR06-070 | 23rd May 2006
Ludwig Staiger

The Kolmogorov complexity of infinite words

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

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

TR06-071 | 25th April 2006
John Hitchcock, A. Pavan

Hardness Hypotheses, Derandomization, and Circuit Complexity

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

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

TR06-072 | 25th February 2006
Henning Fernau

Parameterized Algorithms for Hitting Set: the Weighted Case

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.

... more >>>

TR06-073 | 8th June 2006
Andrej Bogdanov, Luca Trevisan

Average-Case Complexity

Revisions: 1

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

more >>>

TR06-074 | 24th April 2006
Shahar Dobzinski, Noam Nisan

Approximations by Computationally-Efficient VCG-Based Mechanisms

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

TR06-075 | 19th June 2006
Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

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

TR06-076 | 4th May 2006
Noam Nisan

A Note on the computational hardness of evolutionary stable strategies

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

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

Lempel-Ziv Dimension for Lempel-Ziv Compression

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

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

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

TR06-078 | 12th June 2006
Tobias Riege, Jörg Rothe

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem

Revisions: 1

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

TR06-079 | 12th June 2006
Kristoffer Arnsfelt Hansen

Lower Bounds for Circuits with Few Modular Gates using Exponential Sums

We prove that any AC0 circuit augmented with {epsilon log^2 n}
MOD_m gates and with a MAJORITY gate at the output, require size
n^{Omega(log n)} to compute MOD_l, when l has a prime
factor not dividing m and epsilon is sufficiently small. We
also obtain ... more >>>

TR06-080 | 16th June 2006
David Doty

Dimension Extractors

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

TR06-081 | 19th May 2006
Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

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

TR06-082 | 18th June 2006
Prabhu Manyem

Polynomial-Time Maximisation Classes: Syntactic Hierarchy

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

TR06-083 | 16th May 2006
Nils Hebbinghaus, Benjamin Doerr, Frank Neumann

Speeding up Evolutionary Algorithms by Restricted Mutation Operators

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

TR06-084 | 19th June 2006
Frank Neumann, Carsten Witt

Runtime Analysis of a Simple Ant Colony Optimization Algorithm

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

TR06-085 | 15th May 2006
Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry

Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment

Revisions: 1

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

TR06-086 | 25th July 2006
Dmytro Gavinsky, Julia Kempe, Ronald de Wolf

Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

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

TR06-087 | 25th July 2006
Iordanis Kerenidis, Ran Raz

The one-way communication complexity of the Boolean Hidden Matching Problem

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

TR06-088 | 9th July 2006
Per Austrin

Balanced Max 2-Sat might not be the hardest

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

TR06-089 | 16th July 2006
Sofya Raskhodnikova, Adam Smith

A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

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

TR06-090 | 22nd June 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

Non-Mitotic Sets

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<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 >>>

TR06-091 | 29th May 2006
Felix Brandt, Felix Fischer, Markus Holzer

Symmetries and the Complexity of Pure Nash Equilibrium

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

TR06-092 | 5th July 2006
Matthias Englert, Heiko Röglin, Berthold Vöcking

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

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

TR06-093 | 27th July 2006
Takeshi Koshiba, Yoshiharu Seri

Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme

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

TR06-094 | 29th July 2006
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

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

TR06-095 | 25th July 2006
Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

Concurrent Non-Malleable Witness Indistinguishability and its Applications

Revisions: 1

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

TR06-096 | 10th August 2006
Iftach Haitner, Omer Reingold

A New Interactive Hashing Theorem

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

TR06-097 | 9th August 2006
Emanuele Viola

New correlation bounds for GF(2) polynomials using Gowers uniformity

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

TR06-098 | 17th August 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

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

TR06-099 | 17th August 2006
Oded Goldreich

On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits

Revisions: 1

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

TR06-100 | 17th July 2006
Meena Mahajan, Jayalal Sarma

On the Complexity of Rank and Rigidity

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

TR06-101 | 22nd August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Approximation Complexity of Nondense Instances of MAX-CUT

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

TR06-102 | 15th August 2006
Luis Rademacher, Santosh Vempala

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

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

TR06-103 | 5th July 2006
Oded Lachish, Ilan Newman, Asaf Shapira

Space Complexity vs. Query Complexity

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

TR06-104 | 25th August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

On the Sample Complexity of MAX-CUT

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.

more >>>

TR06-105 | 23rd August 2006
Avi Wigderson, David Xiao

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

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

TR06-106 | 18th August 2006
Scott Aaronson

The Learnability of Quantum States

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

TR06-107 | 26th August 2006
Arkadev Chattopadhyay

An improved bound on correlation between polynomials over Z_m and MOD_q

Revisions: 1

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

TR06-108 | 24th August 2006
Dan Gutfreund, Amnon Ta-Shma

New connections between derandomization, worst-case complexity and average-case complexity

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

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

TR06-109 | 29th August 2006
Julia Chuzhoy, Sanjeev Khanna

Hardness of Directed Routing with Congestion

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

TR06-110 | 15th August 2006
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

Improved Algorithms for Optimal Embeddings

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

TR06-111 | 18th July 2006
Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

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

TR06-112 | 22nd August 2006
Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang

Strip Packing vs. Bin Packing

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

TR06-113 | 25th August 2006
Peter Buergisser

On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

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

TR06-114 | 22nd August 2006
Carl Bosley, Yevgeniy Dodis

Does Privacy Require True Randomness?

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

TR06-115 | 26th July 2006
Artur Czumaj, Andrzej Lingas

Finding a Heaviest Triangle is not Harder than Matrix Multiplication

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

TR06-116 | 19th July 2006
Amin Coja-Oghlan

Graph partitioning via adaptive spectral techniques

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

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

Languages with Bounded Multiparty Communication Complexity

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

TR06-118 | 2nd September 2006
Irit Dinur, Madhu Sudan, Avi Wigderson

Robust Local Testability of Tensor Products of LDPC Codes

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

TR06-119 | 13th September 2006
Noga Alon, Oded Schwartz, Asaf Shapira

An Elementary Construction of Constant-Degree Expanders

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

... more >>>

TR06-120 | 12th September 2006
Leslie G. Valiant


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

TR06-121 | 14th September 2006
Charanjit Jutla

A Simple Biased Distribution for Dinur's Construction

TR06-122 | 20th September 2006
Noam Livne

All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

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

TR06-123 | 15th September 2006
Venkatesan Guruswami, Venkatesan Guruswami

Iterative Decoding of Low-Density Parity Check Codes (A Survey)

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

TR06-124 | 25th September 2006
Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Approximation of Global MAX-CSP Problems

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

TR06-125 | 20th September 2006
Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

Low-Depth Witnesses are Easy to Find

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the
notion of non-random information by computational depth, the
difference between the polynomial-time-bounded Kolmogorov
complexity and traditional Kolmogorov complexity We show how to
find satisfying assignments for formulas that have at least one
assignment of logarithmic depth. The converse holds under a
standard ... more >>>

TR06-126 | 2nd October 2006
Piotr Indyk

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

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.

more >>>

TR06-127 | 7th October 2006
Sergey Yekhanin

New Locally Decodable Codes and Private Information Retrieval Schemes

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

TR06-128 | 5th October 2006
Shankar Kalyanaraman, Chris Umans

On obtaining pseudorandomness from error-correcting codes.

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

TR06-129 | 6th October 2006
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The polynomially bounded perfect matching problem is in NC^2

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

TR06-130 | 27th September 2006
Tanmoy Chakraborty, Samir Datta

One-input-face MPCVP is Hard for L, but in LogDCFL

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

TR06-131 | 6th October 2006
Konstantin Pervyshev

On Heuristic Time Hierarchies

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

TR06-132 | 17th October 2006
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

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

TR06-133 | 14th October 2006
Alex Hertel, Alasdair Urquhart

The Resolution Width Problem is EXPTIME-Complete

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

TR06-134 | 18th October 2006
Venkatesan Guruswami, Chris Umans, Salil Vadhan

Extractors and condensers from univariate polynomials

Revisions: 1

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

TR06-135 | 22nd October 2006
Jin-Yi Cai, Pinyan Lu

On Symmetric Signatures in Holographic Algorithms

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

TR06-136 | 22nd October 2006
Mihir Bellare, Oded Goldreich

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

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

TR06-137 | 13th November 2006
Prashant Joshi, Eduardo D. Sontag

Computational aspects of feedback in neural circuits

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

TR06-138 | 13th November 2006
Kei Uchizawa, Rodney Douglas

Energy Complexity and Entropy of Threshold Circuits

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

TR06-139 | 14th November 2006
Shien Jin Ong, Salil Vadhan

Zero Knowledge and Soundness are Symmetric

Revisions: 1

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

TR06-140 | 8th November 2006
Paul Beame, Russell Impagliazzo, Nathan Segerlind

Formula Caching in DPLL

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

TR06-141 | 22nd November 2006
Venkatesan Guruswami, Kunal Talwar

Hardness of Low Congestion Routing in Directed Graphs

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

TR06-142 | 26th October 2006
Olaf Beyersdorff

On the Deduction Theorem and Complete Disjoint NP-Pairs

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

TR06-143 | 15th November 2006
Frank Neumann, Carsten Witt

Ant Colony Optimization and the Minimum Spanning Tree Problem

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

TR06-144 | 21st November 2006
Claire Kenyon-Mathieu, Warren Schudy

How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments

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

TR06-145 | 1st December 2006
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: From Art to Science

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

TR06-146 | 30th September 2006
Christoph Buchheim, Peter J Cameron, Taoyang Wu

On the Subgroup Distance Problem

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

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

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

Revisions: 1

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

To obtain our ... more >>>

TR06-148 | 4th December 2006
Chris Peikert

Limits on the Hardness of Lattice Problems in $\ell_p$ Norms

Revisions: 1

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

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

TR06-149 | 7th December 2006
Lance Fortnow, Rakesh Vohra

The Complexity of Forecast Testing

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

TR06-150 | 4th December 2006
Patrick Briest

Towards Hardness of Envy-Free Pricing

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

TR06-151 | 10th December 2006
Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

The communication complexity of correlation

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

TR06-152 | 6th December 2006
Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

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

more >>>

TR06-153 | 19th October 2006
Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

The Complexity of Generalized Satisfiability for Linear Temporal Logic

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

TR06-154 | 13th December 2006
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam

Uniform Hardness Amplification in NP via Monotone Codes

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

TR06-155 | 15th December 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

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

TR06-156 | 7th December 2006
Tomas Feder, Rajeev Motwani

Finding large cycles in Hamiltonian graphs

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

TR06-157 | 14th December 2006
Lance Fortnow, Rahul Santhanam

Fixed-Polynomial Size Circuit Bounds

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

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

TR06-158 | 8th December 2006
Gyula Gyôr

Representing Boolean OR function by quadratic polynomials modulo 6

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

TR06-159 | 3rd October 2006
Predrag Tosic

Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata

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

TR06-160 | 17th December 2006
Tomas Feder, Phokion G. Kolaitis

Closures and dichotomies for quantified constraints

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

ISSN 1433-8092 | Imprint