Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AVERAGE CASE COMPLEXITY:
Reports tagged with average case complexity:
TR98-069 | 7th December 1998
Rüdiger Reischuk, Thomas Zeugmann

#### An Average-Case Optimal One-Variable Pattern Language Learner

A new algorithm for learning one-variable pattern languages from positive data
is proposed and analyzed with respect to its average-case behavior.
We consider the total learning time that takes into account all
operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions
defining how ... more >>>

TR99-006 | 10th March 1999
Jin-Yi Cai

#### Some Recent Progress on the Complexity of Lattice Problems

We survey some recent developments in the study of
the complexity of lattice problems. After a discussion of some
problems on lattices which can be algorithmically solved
efficiently, our main focus is the recent progress on complexity
results of intractability. We will discuss Ajtai's worst-case/
average-case connections, NP-hardness and non-NP-hardness,
more >>>

TR03-031 | 8th April 2003
Birgit Schelm

#### Average-Case Complexity Theory of Approximation Problems

Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>>

TR03-056 | 29th July 2003
Piotr Berman, Marek Karpinski

#### Approximability of Hypergraph Minimum Bisection

We prove that the problems of minimum bisection on k-uniform
hypergraphs are almost exactly as hard to approximate,
up to the factor k/3, as the problem of minimum bisection
on graphs. On a positive side, our argument gives also the
first approximation ... more >>>

TR06-122 | 20th September 2006
Noam Livne

#### All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

In 1984 Levin put forward a suggestion for a theory of {\em average
case complexity}. In this theory a problem, called a {\em
distributional problem}, is defined as a pair consisting of a
decision problem and a probability distribution over the instances.
Introducing adequate notions of simple distributions and average
more >>>

TR09-057 | 23rd June 2009
Yonatan Bilu, Nathan Linial

#### Are stable instances easy?

We introduce the notion of a stable instance for a discrete
optimization problem, and argue that in many practical situations
only sufficiently stable instances are of interest. The question
then arises whether stable instances of NP--hard problems are
easier to solve. In particular, whether there exist algorithms
that solve correctly ... more >>>

TR10-019 | 19th February 2010
Andrew Drucker

#### A PCP Characterization of AM

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>>

TR10-091 | 14th May 2010
Nikolay Vereshchagin

#### An Encoding Invariant Version of Polynomial Time Computable Distributions

When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,
we usually do not specify how to encode instances by binary strings.
This relies on the empirical observation that the truth of a statement of the form `CIRCUIT-SAT belongs to a complexity class $C$''
more >>>

TR12-086 | 4th July 2012
Shlomi Dolev, Nova Fandina, Dan Gutfreund

#### Succinct Permanent is NEXP-hard with Many Hard Instances

Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue
in theoretical computer science.
In this work, we prove that the Succinct Permanent $\bmod \; p$ is $NEXP$
time hard in the worst case (via randomized polynomial time ... more >>>

TR12-120 | 24th September 2012
Boaz Barak

#### Proof vs. Truth in Computational Complexity

Revisions: 1

In this survey, I discuss the general question of what evidence can we use to predict the answer for open questions in computational complexity, as well as the concrete evidence currently known for two conjectures: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis.

more >>>

TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

#### Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>

ISSN 1433-8092 | Imprint