Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with complete problems:
TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

On Syntactic versus Computational views of Approximability

We attempt to reconcile the two distinct views of approximation
classes: syntactic and computational.
Syntactic classes such as MAX SNP allow for clean complexity-theoretic
results and natural complete problems, while computational classes such
as APX allow us to work with problems whose approximability is
well-understood. Our results give a computational ... more >>>

TR96-039 | 27th June 1996
Carme Alvarez, Raymond Greenlaw

A Compendium of Problems Complete for Symmetric Logarithmic Space

Comments: 2

We provide a compendium of problems that are complete for
symmetric logarithmic space (SL). Complete problems are one method
of studying this class for which programming is nonintuitive. A
number of the problems in the list were not previously known to be
complete. A ... more >>>

TR96-062 | 3rd December 1996
Sanjeev Khanna, Madhu Sudan, David P. Williamson

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of ``constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier ... more >>>

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

Constraint satisfaction: The approximability of minimization problems.

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

TR00-084 | 6th November 2000
Salil Vadhan, Amit Sahai

A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

TR01-092 | 2nd October 2001
Till Tantau

A Note on the Complexity of the Reachability Problem for Tournaments

Deciding whether a vertex in a graph is reachable from another
vertex has been studied intensively in complexity theory and is
well understood. For common types of graphs like directed graphs,
undirected graphs, dags or trees it takes a (possibly
nondeterministic) logspace machine to decide the reachability
problem, and ... more >>>

TR05-018 | 6th February 2005
Oded Goldreich

On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

TR05-138 | 22nd November 2005
Peter B├╝rgisser, Felipe Cucker

Exotic quantifiers, complexity classes, and complete problems

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>

TR06-046 | 1st April 2006
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

A Complete Public-Key Cryptosystem

Comments: 1

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... 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 >>>

TR16-120 | 1st August 2016
Dean Doron, Amir Sarid, Amnon Ta-Shma

On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

Approximating the eigenvalues of a Hermitian operator can be solved
by a quantum logspace algorithm. We introduce the problem of
approximating the eigenvalues of a given matrix in the context of
classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a
certain range of ... more >>>

ISSN 1433-8092 | Imprint