Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2007:
All reports in year 2007:
TR07-001 | 19th November 2006
Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

#### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 2

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

TR07-002 | 8th November 2006
Moti Yung, Yunlei Zhao

#### Concurrent Knowledge-Extraction in the Public-Key Model

Comments: 2

Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and
investigate the relative power of the notion of concurrent knowledge-extraction'' ... more >>>

TR07-003 | 5th January 2007
Jin-Yi Cai, Pinyan Lu

#### Bases Collapse in Holographic Algorithms

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

TR07-004 | 12th January 2007
Lance Fortnow, Rahul Santhanam

#### Time Hierarchies: A Survey

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>

TR07-005 | 17th January 2007
Rahul Santhanam

#### Circuit Lower Bounds for Merlin-Arthur Classes

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

TR07-006 | 12th January 2007
David P. Woodruff

#### New Lower Bounds for General Locally Decodable Codes

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

TR07-007 | 17th January 2007
Jan Krajicek

#### An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams

We prove an exponential lower bound on the size of proofs
in the proof system operating with ordered binary decision diagrams
introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound
applies to semantic derivations operating with sets defined by OBDDs.
We do not assume ... more >>>

TR07-008 | 27th November 2006
Philipp Weis, Neil Immerman

#### Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

It is well-known that every first-order property on words is expressible
using at most three variables. The subclass of properties expressible with
only two variables is also quite interesting and well-studied. We prove
precise structure theorems that characterize the exact expressive power of
first-order logic with two variables on words. ... more >>>

TR07-009 | 8th January 2007
Nathan Segerlind

#### Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Revisions: 1 , Comments: 1

We demonstrate a family of propositional formulas in conjunctive normal form
so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$
to refute using the tree-like OBDD refutation system of
Atserias, Kolaitis and Vardi
with respect to all variable orderings.
All known symbolic quantifier elimination algorithms for satisfiability
generate ... more >>>

TR07-010 | 4th January 2007
Arist Kojevnikov

#### Improved Lower Bounds for Resolution over Linear Inequalities

Revisions: 1

We continue a study initiated by Krajicek of
a Resolution-like proof system working with clauses of linear
inequalities, R(CP). For all proof systems of this kind
Krajicek proved an exponential lower bound that depends
on the maximal absolute value of coefficients in the given proof and
the maximal clause width.

... more >>>

TR07-011 | 19th December 2006
Bodo Manthey

#### On Approximating Restricted Cycle Covers

A cycle cover of a graph is a set of cycles such that every vertex is
part of exactly one cycle. An L-cycle cover is a cycle cover in which
the length of every cycle is in the set L. The weight of a cycle cover
of an edge-weighted graph ... more >>>

TR07-012 | 22nd January 2007
Shachar Lovett, Sasha Sodin

#### Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

It is well known that $\R^N$ has subspaces of dimension
proportional to $N$ on which the $\ell_1$ norm is equivalent to the
$\ell_2$ norm; however, no explicit constructions are known.
Extending earlier work by Artstein--Avidan and Milman, we prove that
such a subspace can be generated using $O(N)$ random bits.

... more >>>

TR07-013 | 6th February 2007
Andris Ambainis, Joseph Emerson

#### Quantum t-designs: t-wise independence in the quantum world

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>

TR07-014 | 23rd January 2007
Amit Chakrabarti

#### Lower Bounds for Multi-Player Pointer Jumping

We consider the $k$-layer pointer jumping problem in the one-way
multi-party number-on-the-forehead communication model. In this problem,
the input is a layered directed graph with each vertex having outdegree
$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em
except} the $i$th. The players must communicate, in the order
$1,2,\ldots,k$, ... more >>>

TR07-015 | 1st March 2007
Oded Goldreich, Or Sheffet

#### On the randomness complexity of property testing

We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine ... more >>>

TR07-016 | 13th February 2007
Prasad Raghavendra

#### A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

{0,1}$into a$(1/2-\eps)$-hard function$Amp(f)$, where$f$is$\gamma$-hard if small circuits fail to compute$f$on at least a$\gamma$fraction of the inputs. Typically,$\eps,\delta$are small (and$\delta=2^{-k}$captures the case ... more >>> TR07-131 | 16th November 2007 Satyen Kale #### Boosting and hard-core set constructions: a simplified approach We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use ... more >>> TR07-132 | 8th December 2007 Emanuele Viola #### The sum of d small-bias generators fools polynomials of degree d We prove that the sum of$d$small-bias generators$L
: \F^s \to \F^n$fools degree-$d$polynomials in$n$variables over a prime field$\F$, for any fixed degree$d$and field$\F$, including$\F = \F_2 =
{0,1}\$.

Our result improves on both the work by Bogdanov and
Viola ... more >>>

TR07-133 | 20th November 2007
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

#### Trapdoors for Hard Lattices and New Cryptographic Constructions

We show how to construct a variety of trapdoor'' cryptographic tools
assuming the worst-case hardness of standard lattice problems (such as
approximating the shortest nonzero vector to within small factors).
The applications include trapdoor functions with \emph{preimage
sampling}, simple and efficient hash-and-sign'' digital signature
schemes, universally composable oblivious transfer, ... more >>>

TR07-134 | 14th December 2007
Jeff Kinne, Dieter van Melkebeek

#### Space Hierarchy Results for Randomized and Other Semantic Models

Revisions: 1

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following.

Let <i>s</i>(<i>n</i>) ... more >>>

TR07-135 | 26th December 2007
Paul Valiant, Paul Valiant

#### Testing Symmetric Properties of Distributions

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and
general enough that a property is testable if and only if the
Canonical Tester tests it''. We construct a Canonical Tester
for the class of symmetric properties of one or two
more >>>

TR07-136 | 28th November 2007
Felix Brandt, Felix Fischer, Markus Holzer

#### Equilibria of Graphical Games with Symmetries

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

TR07-137 | 6th November 2007
Yijia Chen, Jörg Flum, Moritz Müller

#### Lower Bounds for Kernelizations

Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>>

ISSN 1433-8092 | Imprint