Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

Reports tagged with average-case complexity:
TR95-039 | 11th July 1995
Tomoyuki Yamakami

Polynomial Time Samplable Distributions

Revisions: 2

This paper studies distributions which
can be ``approximated'' by sampling algorithms in time polynomial in
the length of their outputs. First, it is known that if
polynomial-time samplable distributions are polynomial-time
computable, then NP collapses to P. This paper shows by a simple
... more >>>

TR96-007 | 29th January 1996
Miklos Ajtai

Generating Hard Instances of Lattice Problems

Comments: 1

We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three ... more >>>

TR96-065 | 13th December 1996
Miklos Ajtai, Cynthia Dwork

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1 , Comments: 1

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose ... more >>>

TR98-037 | 29th June 1998
Johannes Köbler, Rainer Schuler

Average-Case Intractability vs. Worst-Case Intractability

We use the assumption that all sets in NP (or other levels
of the polynomial-time hierarchy) have efficient average-case
algorithms to derive collapse consequences for MA, AM, and various
subclasses of P/poly. As a further consequence we show for
C in {P(PP), PSPACE} that ... more >>>

TR00-081 | 5th September 2000
Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

In this paper we separate many-one reducibility from truth-table
reducibility for distributional problems in DistNP under the
hypothesis that P neq NP. As a first example we consider the
3-Satisfiability problem (3SAT) with two different distributions
on 3CNF formulas. We show that 3SAT using a version of the
standard distribution ... more >>>

TR02-039 | 30th June 2002
Oded Goldreich, Avi Wigderson

Derandomization that is rarely wrong from short advice that is typically good

Comments: 1

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

TR03-066 | 2nd September 2003
Daniele Micciancio

Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

TR04-043 | 20th May 2004
Luca Trevisan

Some Applications of Coding Theory in Computational Complexity

Error-correcting codes and related combinatorial constructs
play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey
results on locally-testable and locally-decodable error-correcting
codes, and their applications to complexity theory and to

Locally decodable codes are error-correcting codes ... more >>>

TR04-087 | 13th October 2004
Alexander Healy, Salil Vadhan, Emanuele Viola

Using Nondeterminism to Amplify Hardness

We revisit the problem of hardness amplification in $\NP$, as
recently studied by O'Donnell (STOC `02). We prove that if $\NP$
has a balanced function $f$ such that any circuit of size $s(n)$
fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then
$\NP$ has a function $f'$ such ... more >>>

TR05-015 | 27th January 2005
Andrej Bogdanov, Luca Trevisan

On Worst-Case to Average-Case Reductions for NP Problems

We show that if an NP-complete problem has a non-adaptive
self-corrector with respect to a samplable distribution then
coNP is contained in NP/poly and the polynomial
hierarchy collapses to the third level. Feigenbaum and
Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion
under the stronger assumption that an
more >>>

TR05-144 | 5th December 2005
Lance Fortnow, Luis Antunes

Time-Bounded Universal Distributions

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions.

more >>>

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

Average-Case Complexity

Revisions: 1

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

more >>>

TR07-089 | 13th September 2007
Parikshit Gopalan, Venkatesan Guruswami

Deterministic Hardness Amplification via Local GMD Decoding

We study the average-case hardness of the class NP against
deterministic polynomial time algorithms. We prove that there exists
some constant $\mu > 0$ such that if there is some language in NP
for which no deterministic polynomial time algorithm can decide L
correctly on a $1- (log n)^{-\mu}$ fraction ... more >>>

TR07-102 | 4th October 2007
Andrej Bogdanov, Muli Safra

Hardness amplification for errorless heuristics

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol "I don't know." A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ > ... more >>>

TR07-117 | 8th November 2007
Edward Hirsch, Dmitry Itsykson

An infinitely-often one-way function based on an average-case assumption

We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>>

TR07-129 | 25th October 2007
Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

Learning Random Monotone DNF

We give an algorithm that with high probability properly learns random monotone t(n)-term
DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ... 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 >>>

TR09-023 | 12th March 2009
Akinori Kawachi, Osamu Watanabe

Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

TR14-100 | 4th August 2014
Salman Beigi, Omid Etesami, Amin Gohari

The Value of Help Bits in Randomized and Average-Case Complexity

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>

TR15-065 | 18th April 2015
Benjamin Rossman, Rocco Servedio, Li-Yang Tan

An average-case depth hierarchy theorem for Boolean circuits

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ ... more >>>

ISSN 1433-8092 | Imprint