Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Complexity classes:
TR94-007 | 12th December 1994
Oded Goldreich, Rafail Ostrovsky, Erez Petrank

Computational Complexity and Knowledge Complexity

We study the computational complexity of languages which have
interactive proofs of logarithmic knowledge complexity. We show that
all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds ... more >>>

TR96-066 | 21st November 1996
Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

Structure in Approximation Classes

The study of the approximability properties of NP-hard
optimization problems has recently made great advances mainly due
to the results obtained in the field of proof checking. In a
recent breakthrough the APX-completeness of several important
optimization problems is proved, thus reconciling `two distinct
views of ... more >>>

TR98-057 | 10th September 1998
Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Characterizing Small Depth and Small Space Classes by Operators of Higher Types

Motivated by the question of how to define an analog of interactive
proofs in the setting of logarithmic time- and space-bounded
computation, we study complexity classes defined in terms of
operators quantifying over oracles. We obtain new
characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ... more >>>

TR98-058 | 2nd August 1998
H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

We introduce "resource-bounded betting games", and propose
a generalization of Lutz's resource-bounded measure in which the choice
of next string to bet on is fully adaptive. Lutz's martingales are
equivalent to betting games constrained to bet on strings in lexicographic
order. We show that if strong pseudo-random number generators exist,
more >>>

TR00-085 | 19th September 2000
Rustam Mubarakzjanov

Probabilistic OBDDs: on Bound of Width versus Bound of Error

Ordered binary decision diagrams (OBDDs) are well established tools to
represent Boolean functions. There are a lot of results concerning
different types of generalizations of OBDDs. The same time, the power
of the most general form of OBDD, namely probabilistic (without bounded
error) OBDDs, is not studied enough. In ... more >>>

TR04-044 | 1st June 2004
Eric Allender, Harry Buhrman, Michal Koucky

What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

We investigate the question of whether one can characterize complexity
classes (such as PSPACE or NEXP) in terms of efficient
reducibility to the set of Kolmogorov-random strings R_C.
We show that this question cannot be posed without explicitly dealing
with issues raised by the choice of universal
machine in the ... more >>>

TR04-053 | 17th June 2004
A. Pavan, N. V. Vinodchandran

Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine
and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.

more >>>

TR05-031 | 1st March 2005
Carme Alvarez, Joaquim Gabarro, Maria Serna

Pure Nash equilibria in games with a large number of actions

We study the computational complexity of deciding the existence of a
Pure Nash Equilibrium in multi-player strategic games.
We address two fundamental questions: how can we represent a game?, and
how can we represent a game with polynomial pay-off functions?
Our results show that the computational complexity of
deciding ... more >>>

TR05-115 | 27th September 2005
Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

The complexity of computing a Nash equilibrium

We resolve the question of the complexity of Nash equilibrium by
showing that the problem of computing a Nash equilibrium in a game
with 4 or more players is complete for the complexity class PPAD.
Our proof uses ideas from the recently-established equivalence
between polynomial-time solvability of normal-form games and
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 >>>

TR15-048 | 14th February 2015
Kamil Khadiev

Width Hierarchy for $k$-OBDD of Small Width

Revisions: 1

In this paper was explored well known model $k$-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by $k$-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as $k$-OBDD and complexity properties of Boolean
function SAF. This function is ... more >>>

TR18-177 | 1st October 2018
Alexander Knop

The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model

Most of the research in communication complexity theory is focused on the
fixed-partition model (in this model the partition of the input between
Alice and Bob is fixed). Nonetheless, the best-partition model (the model
that allows Alice and Bob to choose the partition) has a lot of
more >>>

TR21-068 | 8th May 2021
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

Quantum Proofs of Proximity

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>

ISSN 1433-8092 | Imprint