SIAM Journal on Computing

Assuming that NP $\not\subseteq$ $\cap_{\epsilon > 0}$ BPTIME($2^{n^\epsilon}$), we show that graph min-bisection, dense $k$-subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum ...

An $(n,k)$-bit-fixing source is a distribution $X$ over $\{0,1\}^n$ such that there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly distributed and independent of each other, and the remaining $n-k$ variables are fixed. A ...

In this work we give the first deterministic extractors from a constant number of weak sources whose entropy rate is less than 1/2. Specifically, for every $\delta >0$ we give an explicit construction for extracting randomness from a constant (depending ...

We show that if an NP-complete problem has a nonadaptive self-corrector with respect to any samplable distribution, then coNP is contained in NP/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow [SIAM J. Comput., 22 (...

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. ...

The main result of this paper is a near-optimal derandomization of the affine homomorphism test of Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549-595].

We show that for any groups G and Γ, and any expanding generating set S of G, ...

We study the parallel time-complexity of basic cryptographic primitives such as one-way functions (OWFs) and pseudorandom generators (PRGs). Specifically, we study the possibility of implementing instances of these primitives by $NC^0$ functions, namely,...

We continue the study of the trade-off between the length of probabilistically checkable proofs (PCPs) and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size $n$):

1. We present ...

In this work we look back into the proof of the PCP (probabilistically checkable proofs) theorem, with the goal of finding new proofs that are “more combinatorial” and arguably simpler. For that we introduce the notion of an assignment tester, which is ...

The idea of a SICOMP special issue on randomness and complexity occurred to us when we were in residence at the Radcliffe Institute for Advanced Study at Harvard University during the academic year 2003-2004. We were part of a science cluster in ...