Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2008:
All reports in year 2008:
TR08-001 | 5th January 2008
Ran Raz

#### Elusive Functions and Lower Bounds for Arithmetic Circuits

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

TR08-002 | 19th December 2007

#### Multiparty Communication Complexity of Disjointness

Revisions: 3

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

TR08-003 | 25th December 2007

#### Disjointness is hard in the multi-party number-on-the-forehead model

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

TR08-004 | 2nd January 2008
Zeev Dvir, Amir Shpilka

#### Noisy Interpolating Sets for Low Degree Polynomials

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

TR08-005 | 15th January 2008
Scott Aaronson, Avi Wigderson

#### Algebrization: A New Barrier in Complexity Theory

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

TR08-006 | 18th January 2008
Ran Raz, Amir Yehudayoff

#### Lower Bounds and Separations for Constant Depth Multilinear Circuits

We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth $d$ ... more >>>

TR08-007 | 6th February 2008

#### Limitations of Hardness vs. Randomness under Uniform Reductions

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

TR08-008 | 8th February 2008

#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

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

TR08-009 | 7th December 2007
Per Austrin, Elchanan Mossel

#### Approximation Resistant Predicates From Pairwise Independence

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

TR08-010 | 17th January 2008
Itai Benjamini, Oded Schramm, Asaf Shapira

#### Every Minor-Closed Property of Sparse Graphs is Testable

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

TR08-011 | 21st November 2007
Kazuo Iwama, Suguru Tamaki

#### The Complexity of the Hajos Calculus for Planar Graphs

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

more >>>

TR08-012 | 20th November 2007
Arnab Bhattacharyya

#### A Note on the Distance to Monotonicity of Boolean Functions

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

TR08-013 | 16th January 2008
Anup Rao

#### Parallel Repetition in Projection Games and a Concentration Bound

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

TR08-014 | 26th February 2008
Matei David

#### Separating NOF communication complexity classes RP and NP

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

... more >>>

TR08-015 | 23rd January 2008
Anup Rao

#### Extractors for Low-Weight Affine Sources

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

TR08-016 | 26th February 2008
Alexander Razborov, Alexander A. Sherstov

#### The Sign-Rank of AC^0

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

TR08-017 | 16th December 2007
Thomas Watson, Dieter van Melkebeek

#### A Quantum Time-Space Lower Bound for the Counting Hierarchy

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

TR08-018 | 28th February 2008
Ran Raz

#### A Counterexample to Strong Parallel Repetition

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

TR08-019 | 6th March 2008
Stasys Jukna

#### Entropy of operators or why matrix multiplication is hard for small depth circuits

Revisions: 1

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

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

TR08-020 | 7th March 2008
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

#### Decodability of Group Homomorphisms beyond the Johnson Bound

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

TR08-021 | 3rd March 2008
Shankar Kalyanaraman, Chris Umans

#### The Complexity of Rationalizing Matchings

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

... more >>>

TR08-022 | 9th January 2008
Harry Buhrman, John Hitchcock

#### NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly

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

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

TR08-023 | 10th January 2008
Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

#### Fast Integer Multiplication using Modular Arithmetic

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

TR08-024 | 26th February 2008
Paul Beame, Trinh Huynh

#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

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

TR08-025 | 3rd January 2008
Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

#### New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

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

TR08-026 | 28th February 2008

#### Towards an Optimal Separation of Space and Length in Resolution

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

TR08-027 | 4th December 2007
Till Tantau

#### Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets

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

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

TR08-028 | 5th December 2007
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

#### The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments

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

TR08-029 | 7th January 2008
Christian Glaßer, Christian Reitwießner, Victor Selivanov

#### The Shrinking Property for NP and coNP

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

1. NP ... more >>>

TR08-030 | 16th November 2007
Bruno Durand, Alexander Shen, Andrei Romashchenko

#### Fixed Point and Aperiodic Tilings

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

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

TR08-031 | 14th January 2008
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

#### Computability and Complexity in Self-Assembly

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

TR08-032 | 18th March 2008
Dmitriy Cherukhin

#### Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

TR08-033 | 21st March 2008
Elena Grigorescu, Tali Kaufman, Madhu Sudan

#### 2-Transitivity is Insufficient for Local Testability

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

TR08-034 | 19th January 2008
Dan Gutfreund, Guy Rothblum

#### The Complexity of Local List Decoding

Revisions: 1

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

TR08-035 | 18th February 2008
James I. Lathrop, Jack H. Lutz, Scott M. Summers

#### Strict Self-Assembly of Discrete Sierpinski Triangles

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

TR08-036 | 14th March 2008
Venkatesan Guruswami, Atri Rudra

#### Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

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

TR08-037 | 29th February 2008
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

#### Curves That Must Be Retraced

Revisions: 1

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

TR08-038 | 4th April 2008
Eric Allender, Michal Koucky

#### Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

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

TR08-039 | 7th April 2008
Oded Goldreich, Dana Ron

#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

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

TR08-040 | 3rd April 2008
Sourav Chakraborty, Laszlo Babai

#### Property Testing of Equivalence under a Permutation Group Action

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

TR08-041 | 10th April 2008
Oded Goldreich, Dana Ron

#### On Proximity Oblivious Testing

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

TR08-042 | 6th April 2008
Zeev Dvir

#### Deterministic Extractors for Algebraic Sources

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

TR08-043 | 12th April 2008
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

#### Schemes for Deterministic Polynomial Factoring

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

TR08-044 | 2nd April 2008
Miki Hermann, Reinhard Pichler

#### Complexity of Counting the Optimal Solutions

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

TR08-045 | 23rd April 2008

#### Dense Subsets of Pseudorandom Sets

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

TR08-046 | 14th April 2008
Nikhil R. Devanur, Lance Fortnow

#### A Computational Theory of Awareness and Decision Making

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

TR08-047 | 17th March 2008
Vijay V. Vazirani, Wang Lei

#### Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models

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

TR08-048 | 8th April 2008
Meena Mahajan, B. V. Raghavendra Rao

#### Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

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

TR08-049 | 10th April 2008

#### Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

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

TR08-050 | 12th March 2008
Manoj Prabhakaran, Mike Rosulek

#### Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations

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

TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

#### The Power of Unentanglement

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

TR08-052 | 29th April 2008
Vikraman Arvind, T.C. Vijayaraghavan

#### The Orbit problem is in the GapL Hierarchy

Revisions: 1

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

TR08-053 | 27th March 2008
Stephen A. Fenner, William Gasarch, Brian Postow

#### The complexity of learning SUBSEQ(A)

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

TR08-054 | 13th May 2008
Venkatesan Guruswami, Atri Rudra

#### Concatenated codes can achieve list-decoding capacity

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

TR08-055 | 19th May 2008
Ryan O'Donnell

#### Some Topics in Analysis of Boolean Functions

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

TR08-056 | 22nd April 2008
Beate Bollig

#### On the OBDD complexity of the most significant bit of integer multiplication

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

TR08-057 | 14th May 2008
Alexander A. Sherstov

#### Communication Lower Bounds Using Dual Polynomials

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

TR08-058 | 1st June 2008
Zeev Dvir, Avi Wigderson

#### Kakeya sets, new mergers and old extractors

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

TR08-059 | 20th May 2008
Farid Ablayev, Alexander Vasiliev

#### On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Revisions: 1

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

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

TR08-060 | 10th April 2008

#### Coarse Differentiation and Multi-flows in Planar Graphs

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

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

TR08-061 | 11th June 2008
Paul Beame, Trinh Huynh

#### Multiparty Communication Complexity of AC^0

Revisions: 1

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

TR08-062 | 11th June 2008
Manindra Agrawal, V. Vinay

#### Arithmetic Circuits: A Chasm at Depth Four

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

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

TR08-063 | 21st April 2008
Müller Moritz

#### Valiant-Vazirani Lemmata for Various Logics

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

... more >>>

TR08-064 | 11th July 2008
Or Meir

#### On the Efficiency of Non-Uniform PCPP Verifiers

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

more >>>

TR08-065 | 11th July 2008
Noga Alon, Rina Panigrahy, Sergey Yekhanin

#### Deterministic Approximation Algorithms for the Nearest Codeword Problem

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

TR08-066 | 16th July 2008
Noga Alon, Shai Gutner

#### Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

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

TR08-067 | 4th June 2008
Scott Aaronson

#### On Perfect Completeness for QMA

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

TR08-068 | 3rd July 2008
Lior Malka

#### Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs

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

TR08-069 | 5th August 2008
Klim Efremenko

#### 3-Query Locally Decodable Codes of Subexponential Length

Locally Decodable Codes (LDC) allow one to decode any particular
symbol of the input message by making a constant number of queries
to a codeword, even if a constant fraction of the codeword is
damaged. In recent work ~\cite{Yekhanin08} Yekhanin constructs a
$3$-query LDC with sub-exponential length of size
$\exp(\exp(O(\frac{\log ... more >>> TR08-071 | 6th August 2008 Dana Moshkovitz, Ran Raz #### Two Query PCP with Sub-Constant Error We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error$o(1)$. The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the more >>> TR08-072 | 11th August 2008 Shachar Lovett, Tali Kaufman #### Worst case to Average case reductions for polynomials A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>> TR08-073 | 4th August 2008 Dmitry Itsykson #### Structural complexity of AvgBPP We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>> TR08-074 | 19th July 2008 Neeraj Kayal, Timur Nezhmetdinov #### Factoring groups efficiently We give a polynomial time algorithm that computes a decomposition of a finite group G given in the form of its multiplication table. That is, given G, the algorithm outputs two subgroups A and B of G such that G is the direct product of A ... more >>> TR08-075 | 7th July 2008 Olaf Beyersdorff, Johannes Köbler, Sebastian Müller #### Nondeterministic Instance Complexity and Proof Systems with Advice Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice. In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages? Depending on the complexity of the ... more >>> TR08-076 | 17th June 2008 Ryan Williams #### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>> TR08-077 | 23rd May 2008 Felix Brandt, Felix Fischer, Markus Holzer #### On Iterated Dominance, Matrix Elimination, and Matched Paths We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>> TR08-078 | 15th April 2008 Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer #### Universal Quantum Circuits Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>> TR08-079 | 31st August 2008 Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson #### Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized The classical Direct-Product Theorem for circuits says that if a Boolean function$f:\{0,1\}^n\to\{0,1\}$is somewhat hard to compute on average by small circuits, then the corresponding$k$-wise direct product function$f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$(where each$x_i\in\{0,1\}^n$) is significantly harder to compute on average by slightly smaller ... more >>> TR08-080 | 3rd July 2008 Ido Ben-Eliezer, Rani Hod, Shachar Lovett #### Random low degree polynomials are hard to approximate Revisions: 1 We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over$\F$. We prove that, with very high probability, a random degree$d$polynomial has only an exponentially small correlation with all polynomials of degree$d-1$, for all degrees$d$up to ... more >>> TR08-081 | 11th September 2008 Alexander Razborov #### A simple proof of Bazzi's theorem In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas. The aim of this note is to present a simplified version of his proof. more >>> TR08-082 | 11th September 2008 Paul Beame, Trinh Huynh #### Multiparty Communication Complexity and Threshold Circuit Size of AC^0 Revisions: 2 We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>> TR08-083 | 10th June 2008 Yijia Chen, Jörg Flum #### A logic for PTIME and a parameterized halting problem In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>> TR08-084 | 16th June 2008 Sanjeeb Dash #### On the complexity of cutting plane proofs using split cuts We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case. As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ... more >>> TR08-085 | 19th June 2008 Farid Ablayev, Airat Khasianov, Alexander Vasiliev #### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions Revisions: 1 We consider Generalized Equality, the Hidden Subgroup, and related problems in the context of quantum Ordered Binary Decision Diagrams. For the decision versions of considered problems we show polynomial upper bounds in terms of quantum OBDD width. We apply a new modification of the fingerprinting technique and present the algorithms ... more >>> TR08-086 | 9th July 2008 Vikraman Arvind, Partha Mukhopadhyay #### Quantum Query Complexity of Multilinear Identity Testing Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring$R=\angle{r_1,\cdots,r_k}$where$\{r_1,r_2,\cdots,r_k\}$is an additive generating set for$R$and a multilinear polynomial$f(x_1,\cdots,x_m)$over$R$also accessed as a ... more >>> TR08-087 | 31st July 2008 Tomas Feder, Carlos Subi #### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised) It has been shown that for every perfect matching$M$of the$d$-dimensional$n$-vertex hypercube,$d\geq 2, n=2^d$, there exists a second perfect matching$M'$such that the union of$M$and$M'$forms a Hamiltonian circuit of the$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>> TR08-088 | 13th September 2008 Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie #### Testing Linear-Invariant Non-Linear Properties Revisions: 1 We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including the linearity test and the test for Reed-Muller codes, has mostly focused on such tasks for linear properties. The one exception is a test ... more >>> TR08-089 | 28th September 2008 Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay #### SOLVENCY GAMES Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec- tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With a view to developing the mathematical basics of such a theory, we start with a very simple model more >>> TR08-090 | 6th August 2008 Ulrich Schöpp, Martin Hofmann #### Pointer Programs and Undirected Reachability Revisions: 1 We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the ... more >>> TR08-091 | 10th September 2008 Vitaly Feldman #### On The Power of Membership Queries in Agnostic Learning Revisions: 1 We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning? Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>> TR08-092 | 26th August 2008 Scott Aaronson, John Watrous #### Closed Timelike Curves Make Quantum and Classical Computing Equivalent While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>> TR08-093 | 1st October 2008 Cristopher Moore, Alexander Russell #### A simple constant-probability RP reduction from NP to Parity P The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in$\P^\numP$relies on the fact that, under mild technical conditions on the complexity class$\mathcal{C}$, we have$\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>> TR08-094 | 10th October 2008 Piotr Berman, Marek Karpinski, Alexander Zelikovsky #### 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem. more >>> TR08-095 | 31st October 2008 Brendan Juba, Madhu Sudan #### Universal Semantic Communication II: A Theory of Goal-Oriented Communication Revisions: 1 We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>> TR08-096 | 8th September 2008 Andrew Drucker #### Multitask Efficiencies in the Decision Tree Model In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection$F = \{f_1(x_1), \ldots f_l(x_l)\}$of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>> TR08-097 | 14th November 2008 Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg #### Hierarchy Theorems for Property Testing Revisions: 1 Referring to the query complexity of property testing, we prove the existence of a rich hierarchy of corresponding complexity classes. That is, for any relevant function$q$, we prove the existence of properties that have testing complexity Theta(q). Such results are proven in three standard domains often considered in property ... more >>> TR08-098 | 12th November 2008 Victor Chen #### A Hypergraph Dictatorship Test with Perfect Completeness Revisions: 1 A hypergraph dictatorship test is first introduced by Samorodnitsky and Trevisan and serves as a key component in their unique games based$\PCP$construction. Such a test has oracle access to a collection of functions and determines whether all the functions are the same dictatorship, or all their low degree ... more >>> TR08-099 | 19th November 2008 Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena #### Trading GRH for algebra: algorithms for factoring polynomials and related structures In this paper we develop techniques that eliminate the need of the Generalized Riemann Hypothesis (GRH) from various (almost all) known results about deterministic polynomial factoring over finite fields. Our main result shows that given a polynomial f(x) of degree n over a finite field k, we ... more >>> TR08-100 | 14th November 2008 Chris Peikert #### Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem We construct public-key cryptosystems that are secure assuming the \emph{worst-case} hardness of approximating the length of a shortest nonzero vector in an$n$-dimensional lattice to within a small$\poly(n)$factor. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a \emph{special class} of lattices ... more >>> TR08-101 | 20th November 2008 Marek Karpinski, Warren Schudy #### Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>> TR08-102 | 9th November 2008 Adi Akavia #### Finding Significant Fourier Transform Coefficients Deterministically and Locally Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the$O(N\log N)$running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear ... more >>> TR08-103 | 22nd November 2008 Luca Trevisan, Madhur Tulsiani, Salil Vadhan #### Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution We show that every high-entropy distribution is indistinguishable from an efficiently samplable distribution of the same entropy. Specifically, we prove that if$D$is a distribution over$\{ 0,1\}^n$of min-entropy at least$n-k$, then for every$S$and$\epsilon$there is a circuit$C$of size at most$S\cdot ... more >>>

TR08-104 | 23rd November 2008

#### CSP Gaps and Reductions in the Lasserre Hierarchy

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

TR08-105 | 26th November 2008

#### List Decoding Tensor Products and Interleaved Codes

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

TR08-106 | 12th November 2008
Jack H. Lutz

#### A Divergence Formula for Randomness and Dimension

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

TR08-107 | 12th November 2008

#### Optimal Proof Systems and Complete Languages

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

TR08-108 | 19th November 2008

#### An Almost Optimal Rank Bound for Depth-3 Identities

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

TR08-109 | 10th November 2008
Marc Kaplan, Sophie Laplante

#### Kolmogorov complexity and combinatorial methods in communication complexity

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

TR08-110 | 19th November 2008
Chris Calabro

#### A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths

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

TR08-111 | 14th November 2008
Shachar Lovett, Tali Kaufman

#### The List-Decoding Size of Reed-Muller Codes

Revisions: 2

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

ISSN 1433-8092 | Imprint