Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Joshua Cook:

TR22-093 | 28th June 2022
Joshua Cook

More Verifier Efficient Interactive Protocols For Bounded Space

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. ... more >>>

TR22-014 | 8th February 2022
Joshua Cook, Dana Moshkovitz

Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

We prove for some constant $a > 1$, for all $k \leq a$,
$$\mathbf{MATIME}[n^{k + o(1)}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})],$$
for some specific $o(1)$ function. This improves on the Santhanam lower bound, which says there exists constant $c$ such that for all $k > 1$:
$$\mathbf{MATIME}[n^{c k}] / 1 ... more >>>

TR20-122 | 8th August 2020
Joshua Cook

Size Bounds on Low Depth Circuits for Promise Majority

Revisions: 3

We give two results on the size of AC0 circuits computing promise majority. $\epsilon$-promise majority is majority promised that either at most an $\epsilon$ fraction of the input bits are 1, or at most $\epsilon$ are 0.

First, we show super quadratic lower bounds on both monotone and general depth ... more >>>

ISSN 1433-8092 | Imprint