Oded Goldreich, Rafail Ostrovsky, Erez Petrank

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

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

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

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

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

H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

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

Rustam Mubarakzjanov

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

Eric Allender, Harry Buhrman, Michal Koucky

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

A. Pavan, N. V. Vinodchandran

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.

Carme Alvarez, Joaquim Gabarro, Maria Serna

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

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

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

Peter Bürgisser, Felipe Cucker

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

Kamil Khadiev

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

Alexander Knop

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

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

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

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:

\begin{itemize}

\item If there exists a perfect (imperfect) $IO$ that is computationally secure ...
more >>>