Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR94-015 | 12th December 1994
Miklos Ajtai

Symmetric Systems of Linear Equations modulo $p$


Suppose that $p$ is a prime number $A$ is a finite set
with $n$ elements
and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the
elements of
$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an
$n$ is sufficiently large.) We will ... more >>>


TR94-003 | 12th December 1994
Noam Nisan, Amnon Ta-Shma

Symmetric Logspace is Closed Under Complement

We present a Logspace, many-one reduction from the undirected
st-connectivity problem to its complement. This shows that
$SL=co-SL$

more >>>

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



previous PreviousNext next


ISSN 1433-8092 | Imprint