All reports in year 2002:

__
TR02-001
| 8th January 2002
__

Cynthia Dwork, Moni Naor#### Zaps and Their Applications

__
TR02-002
| 3rd January 2002
__

Howard Barnum, Michael Saks#### A lower bound on the quantum query complexity of read-once functions

__
TR02-003
| 24th December 2001
__

Eli Ben-Sasson, Yonatan Bilu#### A Gap in Average Proof Complexity

__
TR02-004
| 2nd November 2001
__

Till Tantau#### A Note on the Power of Extra Queries to Membership Comparable Sets

__
TR02-005
| 3rd January 2002
__

A. Pavan, Alan L. Selman#### Bi-Immunity Separates Strong NP-Completeness Notions

__
TR02-006
| 8th November 2001
__

Philippe Moser#### Random nondeterministic real functions and Arthur Merlin games

Revisions: 1

__
TR02-007
| 14th January 2002
__

Pavel Pudlak#### Monotone complexity and the rank of matrices

Comments: 1

__
TR02-008
| 11th January 2002
__

Valentine Kabanets#### Derandomization: A Brief Overview

__
TR02-009
| 17th January 2002
__

Petr Savicky#### On determinism versus unambiquous nondeterminism for decision trees

__
TR02-010
| 21st January 2002
__

Albert Atserias, Maria Luisa Bonet#### On the Automatizability of Resolution and Related Propositional Proof Systems

__
TR02-011
| 14th October 2001
__

Boris Ryabko#### The nonprobabilistic approach to learning the best prediction.

__
TR02-012
| 3rd February 2002
__

Ran Raz#### On the Complexity of Matrix Product

__
TR02-013
| 30th January 2002
__

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett#### Quantum and Stochastic Programs of Bounded Width

Revisions: 1

__
TR02-014
| 10th December 2001
__

Klaus Weihrauch#### Computational Complexity on Computable Metric Spaces

Revisions: 1

__
TR02-015
| 13th February 2002
__

Philippe Moser#### ZPP is hard unless RP is small

Revisions: 1

__
TR02-016
| 30th January 2002
__

Alina Beygelzimer, Mitsunori Ogihara#### On the Enumerability of the Determinant and the Rank

__
TR02-017
| 12th March 2002
__

Aggelos Kiayias, Moti Yung#### Cryptographic Hardness based on the Decoding of Reed-Solomon Codes with Applications

__
TR02-018
| 22nd March 2002
__

Piotr Berman, Marek Karpinski, Yakov Nekrich#### Approximating Huffman Codes in Parallel

__
TR02-019
| 20th March 2002
__

Nader Bshouty, Lynn Burroughs#### On the proper learning of axis parallel concepts

__
TR02-020
| 13th March 2002
__

Elizaveta Okol'nishnikova#### On one lower bound for branching programs

__
TR02-021
| 11th April 2002
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Space Efficient Algorithms for Directed Series-Parallel Graphs

__
TR02-022
| 12th April 2002
__

Henry Markram#### On the Computational Power of Recurrent Circuits of Spiking Neurons

__
TR02-023
| 16th April 2002
__

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal#### Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

__
TR02-024
| 24th April 2002
__

Piotr Indyk#### List-decoding in Linear Time

__
TR02-025
| 26th April 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani#### Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

__
TR02-026
| 7th April 2002
__

Boaz Barak, Yehuda Lindell#### Strict Polynomial-time in Simulation and Extraction

Revisions: 2

__
TR02-027
| 30th April 2002
__

Irit Dinur, Venkatesan Guruswami, Subhash Khot#### Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

__
TR02-028
| 15th May 2002
__

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek#### Power from Random Strings

Revisions: 1

__
TR02-029
| 3rd June 2002
__

Marek Karpinski, Yakov Nekrich#### Parallel Construction of Minimum Redundancy Length-Limited Codes

__
TR02-030
| 3rd June 2002
__

Lars Engebretsen, Jonas Holmerin, Alexander Russell#### Inapproximability Results for Equations over Finite Groups

Revisions: 1

__
TR02-031
| 30th April 2002
__

Vikraman Arvind, Venkatesh Raman#### Approximate Counting small subgraphs of bounded treewidth and related problems

Revisions: 1

__
TR02-032
| 17th April 2002
__

Andrei Bulatov#### Tractable Constraint Satisfaction Problems on a 3-element set

__
TR02-033
| 11th June 2002
__

Beate Bollig#### A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

__
TR02-034
| 18th April 2002
__

Andrei Bulatov#### Mal'tsev constraints are tractable

__
TR02-035
| 27th May 2002
__

Albert Atserias, Víctor Dalmau#### A Combinatorial Characterization of Resolution Width

__
TR02-036
| 30th May 2002
__

Stephen A. Fenner#### PP-lowness and a simple definition of AWPP

__
TR02-037
| 21st May 2002
__

Vikraman Arvind, Piyush Kurur#### Graph Isomorphism is in SPP

__
TR02-038
| 5th June 2002
__

Rahul Santhanam#### Resource Tradeoffs and Derandomization

Revisions: 1

__
TR02-039
| 30th June 2002
__

Oded Goldreich, Avi Wigderson#### Derandomization that is rarely wrong from short advice that is typically good

Comments: 1

__
TR02-040
| 20th June 2002
__

Lars Engebretsen, Jonas Holmerin#### Three-Query PCPs with Perfect Completeness over non-Boolean Domains

__
TR02-041
| 2nd July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon#### A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

__
TR02-042
| 7th June 2002
__

Dima Grigoriev#### Public-key cryptography and invariant theory

__
TR02-043
| 11th July 2002
__

Dalit Naor, Moni Naor, Jeff Lotspiech#### Revocation and Tracing Schemes for Stateless Receivers

__
TR02-044
| 16th July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### A Polynomial Time Approximation Scheme for Subdense MAX-CUT

__
TR02-045
| 8th July 2002
__

Daniele Micciancio, Erez Petrank#### Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol

__
TR02-046
| 16th July 2002
__

Marek Karpinski#### On Approximability of Minimum Bisection Problem

__
TR02-047
| 3rd August 2002
__

Oded Goldreich#### The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

__
TR02-048
| 31st July 2002
__

Noga Alon, Oded Goldreich, Yishay Mansour#### Almost $k$-wise independence versus $k$-wise independence

__
TR02-049
| 4th August 2002
__

Oded Goldreich, Vered Rosen#### On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

__
TR02-050
| 5th August 2002
__

Oded Goldreich, Madhu Sudan#### Locally Testable Codes and PCPs of Almost-Linear Length

__
TR02-051
| 16th July 2002
__

Chris Pollett#### Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

__
TR02-052
| 3rd September 2002
__

Vince Grolmusz#### Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Revisions: 1

__
TR02-053
| 20th July 2002
__

Lars Engebretsen, Venkatesan Guruswami#### Is Constraint Satisfaction Over Two Variables Always Easy?

__
TR02-054
| 5th September 2002
__

Detlef Sieling#### Minimization of Decision Trees is Hard to Approximate

__
TR02-055
| 13th September 2002
__

Valentine Kabanets, Russell Impagliazzo#### Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

__
TR02-056
| 19th September 2002
__

Todd Ebert, Wolfgang Merkle, Heribert Vollmer#### On the Autoreducibility of Random Sequences

__
TR02-057
| 19th September 2002
__

Richard J. Lipton, Anastasios Viglas#### Non-uniform Depth of Polynomial Time and Space Simulations

__
TR02-058
| 25th September 2002
__

Philippe Moser#### A generalization of Lutz's measure to probabilistic classes

__
TR02-059
| 9th August 2002
__

Iordanis Kerenidis, Ronald de Wolf#### Exponential Lower Bound for 2-Query Locally Decodable Codes

__
TR02-060
| 15th July 2002
__

Ke Yang#### New Lower Bounds for Statistical Query Learning

__
TR02-061
| 14th November 2002
__

Miklos Ajtai#### A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

__
TR02-062
| 19th November 2002
__

Andrew Chi-Chih Yao#### Classical Physics and the Church-Turing Thesis

__
TR02-063
| 3rd December 2002
__

Oded Goldreich#### Zero-Knowledge twenty years after its invention

__
TR02-064
| 14th November 2002
__

Andrej Bogdanov, Luca Trevisan#### Lower Bounds for Testing Bipartiteness in Dense Graphs

__
TR02-065
| 26th November 2002
__

Olivier Powell#### Measure on P revisited

__
TR02-066
| 24th October 2002
__

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay#### Circuits on Cylinders

__
TR02-067
| 5th October 2002
__

Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf#### k-Approximating Circuits

__
TR02-068
| 10th December 2002
__

Tobias Riege, Jörg Rothe#### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

Revisions: 2

__
TR02-069
| 14th November 2002
__

Luca Trevisan#### A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

__
TR02-070
| 13th December 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### 9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

__
TR02-071
| 6th June 2002
__

Bruno Codenotti, Igor E. Shparlinski#### Non-approximability of the Permanent of Structured Matrices over Finite Fields

__
TR02-072
| 12th November 2002
__

Scott Aaronson#### Quantum Lower Bound for Recursive Fourier Sampling

__
TR02-073
| 12th December 2002
__

Janka Chlebíková, Miroslav Chlebík#### Approximation Hardness for Small Occurrence Instances of NP-Hard Problem

__
TR02-074
| 26th December 2002
__

Andrew Chi-Chih Yao#### On the Power of Quantum Fingerprinting

Cynthia Dwork, Moni Naor

A zap is a two-round, witness-indistinguishable protocol in which

the first round, consisting of a message from the verifier to the

prover, can be fixed ``once-and-for-all" and applied to any instance,

and where the verifier does not use any private coins.

We present a zap for every language in NP, ...
more >>>

Howard Barnum, Michael Saks

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' ... more >>>

Eli Ben-Sasson, Yonatan Bilu

We present the first example of a natural distribution on instances

of an NP-complete problem, with the following properties.

With high probability a random formula from this

distribution (a) is unsatisfiable,

(b) has a short proof that can be found easily, and (c) does not have a short

(general) resolution ...
more >>>

Till Tantau

A language is called k-membership comparable if there exists a

polynomial-time algorithm that excludes for any k words one of

the 2^k possibilities for their characteristic string.

It is known that all membership comparable languages can be

reduced to some P-selective language with polynomially many

adaptive queries. We show however ...
more >>>

A. Pavan, Alan L. Selman

We prove that if for some epsilon > 0 NP contains a set that is

DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing

complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo

(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the

same consequence using strong ...
more >>>

Philippe Moser

We construct a nondeterministic analogue to \textbf{APP}, denoted

\textbf{NAPP}; which is the set of all real valued functions

$f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$,

by a probabilistic nondeterministic transducer, in time poly($n,1^{k}$).

We show that the subset of all Boolean ...
more >>>

Pavel Pudlak

The rank of a matrix has been used a number of times to prove lower

bounds on various types of complexity. In particular it has been used

for the size of monotone formulas and monotone span programs. In most

cases that this approach was used, there is not a single ...
more >>>

Valentine Kabanets

This survey focuses on the recent (after 1998) developments in

the area of derandomization, with the emphasis on the derandomization of

time-bounded randomized complexity classes.

Petr Savicky

Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the

sum of the minimum number of monomials in a disjunctive normal form

for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition

of the Boolean cube into disjoint subcubes such that $f$ is constant on

more >>>

Albert Atserias, Maria Luisa Bonet

Having good algorithms to verify tautologies as efficiently as possible

is of prime interest in different fields of computer science.

In this paper we present an algorithm for finding Resolution refutations

based on finding tree-like Res(k) refutations. The algorithm is based on

the one of Beame and Pitassi \cite{BP96} ...
more >>>

Boris Ryabko

The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs

to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted

using information on the word $x_1, x_2, ...., x_t $ only. We use the game

theoretical interpretation which can be traced to Laplace where there ...
more >>>

Ran Raz

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of

any arithmetic circuit for the product of two matrices,

over the real or complex numbers, as long as the circuit doesn't

use products with field elements of absolute value larger than 1

(where $m \times m$ is ...
more >>>

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

We prove upper and lower bounds on the power of quantum and stochastic

branching programs of bounded width. We show any NC^1 language can

be accepted exactly by a width-2 quantum branching program of

polynomial length, in contrast to the classical case where width 5 is

necessary unless \NC^1=\ACC. ...
more >>>

Klaus Weihrauch

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

Philippe Moser

We use Lutz's resource bounded measure theory to prove that either \tbf{RP} is

small or \tbf{ZPP} is hard. More precisely we prove that if \tbf{RP} has not p-measure zero, then \tbf{EXP} is contained

in $\mbf{ZPP}/n$.

We also show that if \tbf{RP} has not p-measure zero,

\tbf{EXP} equals ...
more >>>

Alina Beygelzimer, Mitsunori Ogihara

We investigate the complexity of enumerative approximation of

two elementary problems in linear algebra, computing the rank

and the determinant of a matrix. In particular, we show that

if there exists an enumerator that, given a matrix, outputs a

list of constantly many numbers, one of which is guaranteed to

more >>>

Aggelos Kiayias, Moti Yung

We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem -- PR) from a cryptographic hardness perspective. First, following the standard methodology for constructing cryptographically strong primitives, we formulate a decisional intractability assumption related to the PR problem. Then, based on this assumption we show: (i) hardness ... more >>>

Piotr Berman, Marek Karpinski, Yakov Nekrich

In this paper we present some new results on the approximate parallel

construction of Huffman codes. Our algorithm achieves linear work

and logarithmic time, provided that the initial set of elements

is sorted. This is the first parallel algorithm for that problem

with the optimal time and ...
more >>>

Nader Bshouty, Lynn Burroughs

We study the proper learnability of axis parallel concept classes

in the PAC learning model and in the exact learning model with

membership and equivalence queries. These classes include union of boxes,

DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$

we ...
more >>>

Elizaveta Okol'nishnikova

The method of obtaining lower bounds on the complexity

of Boolean functions for nondeterministic branching programs

is proposed.

A nonlinear lower bound on the complexity of characteristic

functions of Reed--Muller codes for nondeterministic

branching programs is obtained.

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

The subclass of directed series-parallel graphs plays an important role in

computer science. Whether a given graph is series-parallel is a

well studied problem in algorithmic graph theory, for which fast sequential and

parallel algorithms have been developed in a sequence of papers.

Also methods are known to solve ...
more >>>

Henry Markram

Understanding the structure of real-time neural computation in

highly recurrent neural microcircuits that consist of complex

heterogeneous components has remained a serious challenge for

computational modeling. We propose here a new conceptual framework

that strongly differs from all previous approaches based on

computational models inspired ...
more >>>

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

We prove a quasi-polynomial lower bound on the size of bounded-depth

Frege proofs of the pigeonhole principle $PHP^{m}_n$ where

$m= (1+1/{\polylog n})n$.

This lower bound qualitatively matches the known quasi-polynomial-size

bounded-depth Frege proofs for these principles.

Our technique, which uses a switching lemma argument like other lower bounds

for ...
more >>>

Piotr Indyk

Spielman showed that one can construct error-correcting codes capable

of correcting a constant fraction $\delta << 1/2$ of errors,

and that are encodable/decodable in linear time.

Guruswami and Sudan showed that it is possible to correct

more than $50\%$ of errors (and thus exceed the ``half of the ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well ...
more >>>

Boaz Barak, Yehuda Lindell

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>

Irit Dinur, Venkatesan Guruswami, Subhash Khot

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is

to find a minimum subset of vertices that ``hits'' every edge. We

show that for every integer $k \geq 5$, E$k$-Vertex-Cover is

NP-hard to approximate within a factor of $(k-3-\epsilon)$, for

an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

We consider sets of strings with high Kolmogorov complexity, mainly

in resource-bounded settings but also in the traditional

recursion-theoretic sense. We present efficient reductions, showing

that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, ...
more >>>

Marek Karpinski, Yakov Nekrich

This paper presents new results on parallel constructions of the

length-limited prefix-free codes with the minimum redundancy.

We describe an algorithm for the construction of length-limited codes

that works in $O(L)$ time with $n$ processors for $L$ the

maximal codeword length.

We also describe an algorithm for a construction ...
more >>>

Lars Engebretsen, Jonas Holmerin, Alexander Russell

An equation over a finite group G is an expression of form

w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted

variable, or a constant from G; such an equation is satisfiable

if there is a setting of the variables to values in G ...
more >>>

Vikraman Arvind, Venkatesh Raman

We give a randomized approximation algorithm taking

$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a

$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph

$G$ with approximation ratio $1/k^{O(k)}$ and error probability

inverse exponential in $n$. This algorithm is based on ...
more >>>

Andrei Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

Beate Bollig

Branching programs are a well-established computation

model for boolean functions, especially read-once

branching programs (BP1s) have been studied intensively.

A very simple function $f$ in $n^2$ variables is

exhibited such that both the function $f$ and its negation

$\neg f$ can be computed by $\Sigma^3_p$-circuits,

the ...
more >>>

Andrei Bulatov

A wide variety of combinatorial problems can be represented in the form of the Constraint Satisfaction Problem (CSP). The general CSR is known to be NP-complete, however, some restrictions on the possible form of constraints may lead to a tractable subclass. Jeavons and coauthors have shown that the complexity of ... more >>>

Albert Atserias, Víctor Dalmau

We provide a characterization of the resolution

width introduced in the context of Propositional Proof Complexity

in terms of the existential pebble game introduced

in the context of Finite Model Theory. The characterization

is tight and purely combinatorial. Our

first application of this result is a surprising

proof that the ...
more >>>

Stephen A. Fenner

We show that the counting classes AWPP and APP [Li 1993] are more robust

than previously thought. Our results identify asufficient condition for

a language to be low for PP, and we show that this condition is at least

as weak as other previously studied criteria. Our results imply that

more >>>

Vikraman Arvind, Piyush Kurur

We show that Graph Isomorphism is in the complexity class

SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for

each $k\geq 2$). We derive this result as a corollary of a more

general result: we show that a {\em generic problem} $\FINDGROUP$ has

an $\FP^{\SPP}$ ...
more >>>

Rahul Santhanam

We consider uniform assumptions for derandomization. We provide

intuitive evidence that BPP can be simulated non-trivially in

deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE

implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP

= P. These results extend and complement earlier work of ...
more >>>

Oded Goldreich, Avi Wigderson

For every $\epsilon>0$,

we present a {\em deterministic}\/ log-space algorithm

that correctly decides undirected graph connectivity

on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.

The same holds for every problem in Symmetric Log-space (i.e., $\SL$).

Making no assumptions (and in particular not assuming the ... more >>>

Lars Engebretsen, Jonas Holmerin

We study non-Boolean PCPs that have perfect completeness and read

three positions from the proof. For the case when the proof consists

of values from a domain of size d for some integer constant d

>= 2, we construct a non-adaptive PCP with perfect completeness

more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

We design a polynomial time approximation scheme (PTAS) for

the problem of Metric MIN-BISECTION of dividing a given finite metric

space into two halves so as to minimize the sum of distances across

that partition. The method of solution depends on a new metric placement

partitioning ...
more >>>

Dima Grigoriev

Public-key crypto

Contact: dima@maths.univ-rennes1.fr

Author: Dima Grigoriev

Title: Public-key cryptography and invariant theory

Abstract: Public-key cryptosystems are suggested based on invariants of group

representations

Dalit Naor, Moni Naor, Jeff Lotspiech

We deal with the problem of a center sending a secret message to

a group of users such that some subset of the users is considered

revoked and should not be able to obtain the content of the

message. We concentrate on the stateless receiver case, where

the users do ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that the subdense instances of MAX-CUT of average

degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS).

We extend this result also to show that the instances of general 2-ary

maximum constraint satisfaction problems (MAX-CSP) of the same average

density have PTASs. Our results ...
more >>>

Daniele Micciancio, Erez Petrank

We show how to efficiently transform any public coin honest verifier

zero knowledge proof system into a proof system that is concurrent

zero-knowledge with respect to any (possibly cheating) verifier via

black box simulation. By efficient we mean that our transformation

incurs only an additive overhead, ...
more >>>

Marek Karpinski

We survey some recent results on the complexity of computing

approximate solutions for instances of the Minimum Bisection problem

and formulate some intriguing and still open questions about the

approximability status of that problem. Some connections to other

optimization problems are also indicated.

Oded Goldreich

We consider the function ensembles emerging from the

construction of Goldreich, Goldwasser and Micali (GGM),

when applied to an arbitrary pseudoramdon generator.

We show that, in general, such functions

fail to yield correlation intractable ensembles.

Specifically, it may happen that, given a description of such a ...
more >>>

Noga Alon, Oded Goldreich, Yishay Mansour

We say that a distribution over $\{0,1\}^n$

is almost $k$-wise independent

if its restriction to every $k$ coordinates results in a

distribution that is close to the uniform distribution.

A natural question regarding almost $k$-wise independent

distributions is how close they are to some $k$-wise

independent distribution. We show ...
more >>>

Oded Goldreich, Vered Rosen

Assuming the inractability of factoring, we show that

the output of the exponentiation modulo a composite function

$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,

even when its input is restricted to be half the size.

This result is equivalent to the simultaneous hardness of the upper

half of the bits ...
more >>>

Oded Goldreich, Madhu Sudan

Locally testable codes are error-correcting codes that admit

very efficient codeword tests. Specifically, using a constant

number of (random) queries, non-codewords are rejected with

probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial

core of PCPs. However, the relation is ...
more >>>

Chris Pollett

The use of Nepomnjascij's Theorem in the proofs of independence results

for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here ...
more >>>

Vince Grolmusz

Elementary symmetric polynomials $S_n^k$ are used as a

benchmark for the bounded-depth arithmetic circuit model of computation.

In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$

can be computed with much fewer multiplications than over any field, if

the coefficients of monomials $x_{i_1}x_{i_2}\cdots x_{i_k}$ ...
more >>>

Lars Engebretsen, Venkatesan Guruswami

By the breakthrough work of Håstad, several constraint satisfaction

problems are now known to have the following approximation resistance

property: satisfying more clauses than what picking a random

assignment would achieve is NP-hard. This is the case for example for

Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ...
more >>>

Detlef Sieling

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>

Valentine Kabanets, Russell Impagliazzo

We show that derandomizing Polynomial Identity Testing is,

essentially, equivalent to proving circuit lower bounds for

NEXP. More precisely, we prove that if one can test in polynomial

time (or, even, nondeterministic subexponential time, infinitely

often) whether a given arithmetic circuit over integers computes an

identically zero polynomial, then either ...
more >>>

Todd Ebert, Wolfgang Merkle, Heribert Vollmer

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

Richard J. Lipton, Anastasios Viglas

We discuss some connections between polynomial time and non-uniform, small depth circuits. A connection is shown with simulating deterministic time in small space. The well known result of Hopcroft, Paul and Valiant showing that space is more powerful than time can be improved, by making an assumption about the connection ... more >>>

Philippe Moser

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes

C

such as BPP , BPE and BPEXP. Unlike former attempts,

all our measure notions satisfy all three Lutz's measure axioms, that is

every singleton {L} has measure zero ...
more >>>

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query

locally decodable codes. Goldreich et al. recently proved such bounds

for the special case of linear locally decodable codes.

Our proof shows that a 2-query locally decodable code can be decoded

with only 1 quantum query, and then ...
more >>>

Ke Yang

We prove two lower bounds on the Statistical Query (SQ) learning

model. The first lower bound is on weak-learning. We prove that for a

concept class of SQ-dimension $d$, a running time of

$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is

defined to be the maximum number ...
more >>>

Miklos Ajtai

A measure $\mu_{n}$ on $n$-dimensional lattices with

determinant $1$ was introduced about fifty years ago to prove the

existence of lattices which contain points from certain sets. $\mu_{n}$

is the unique probability measure on lattices with determinant $1$ which

is invariant under linear transformations with determinant $1$, where a

more >>>

Andrew Chi-Chih Yao

Would physical laws permit the construction of computing machines

that are capable of solving some problems much faster than the

standard computational model? Recent evidence suggests that this

might be the case in the quantum world. But the question is of

great interest even in the realm of classical physics. ...
more >>>

Oded Goldreich

Zero-knowledge proofs are proofs that are both convincing and yet

yield nothing beyond the validity of the assertion being proven.

Since their introduction about twenty years ago,

zero-knowledge proofs have attracted a lot of attention

and have, in turn, contributed to the development of other

areas of cryptography and complexity ...
more >>>

Andrej Bogdanov, Luca Trevisan

We consider the problem of testing bipartiteness in the adjacency

matrix model. The best known algorithm, due to Alon and Krivelevich,

distinguishes between bipartite graphs and graphs that are

$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$

queries. We show that this is optimal for non-adaptive algorithms,

up to the ...
more >>>

Olivier Powell

We revisit the problem of generalising Lutz's resource bounded measure

(rbm) to small complexity classes.

We propose a definition of a perfect rbm on P,

and give sufficient and necessary conditions for such a measure to exist.

We also revisit $\mu_\tau$, an rbm for P

defined in previous articles (c.f. ...
more >>>

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

We consider the computational power of constant width polynomial

size cylindrical circuits and nondeterministic branching programs.

We show that every function computed by a Pi2 o MOD o AC0 circuit

can also be computed by a constant width polynomial size cylindrical

nondeterministic branching program (or cylindrical circuit) and

that ...
more >>>

Marco Cadoli, Francesco Donini, Paolo Liberatore, Marco Schaerf

In this paper we study the problem of approximating a boolean

function using the Hamming distance as the approximation measure.

Namely, given a boolean function f, its k-approximation is the

function f^k returning true on the same points in which f does,

plus all points whose Hamming distance from the ...
more >>>

Tobias Riege, Jörg Rothe

We prove that the exact versions of the domatic number problem are complete

for the levels of the boolean hierarchy over NP. The domatic number

problem, which arises in the area of computer networks, is the problem of

partitioning a given graph into a maximum number ...
more >>>

Luca Trevisan

We describe a deterministic algorithm that, for constant k,

given a k-DNF or k-CNF formula f and a parameter e, runs in time

linear in the size of f and polynomial in 1/e and returns an

estimate of the fraction of satisfying assignments for f up to ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that MAX-3SAT can be approximated in polynomial time

within a factor 9/8 on random instances.

Bruno Codenotti, Igor E. Shparlinski

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

Scott Aaronson

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside ... more >>>

Janka Chlebíková, Miroslav Chlebík

The paper contributes to the systematic study (started by Berman and

Karpinski) of explicit approximability lower bounds for small occurrence optimization

problems. We present parametrized reductions for some packing and

covering problems, including 3-Dimensional Matching, and prove the best

known inapproximability results even for highly restricted versions of ...
more >>>

Andrew Chi-Chih Yao

In the simultaneous message model, two parties holding $n$-bit integers

$x,y$ send messages to a third party, the {\it referee}, enabling

him to compute a boolean function $f(x,y)$. Buhrman et al

[BCWW01] proved the remarkable result that, when $f$ is the

equality function, the referee can solve this problem by ...
more >>>