Volume 36; Issue 4

SIAM Journal on Computing

Volume 36; Issue 4
1

Special Issue on Randomness and Complexity

Goldreich, Oded, Sudan, Madhu
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 52 KB
english, 2006
2

Cryptography in $NC^0$

Applebaum, Benny, Ishai, Yuval, Kushilevitz, Eyal
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 430 KB
english, 2006
4

Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

Khot, Subhash
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 475 KB
english, 2006
6

Extracting Randomness Using Few Independent Sources

Barak, Boaz, Impagliazzo, Russell, Wigderson, Avi
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 310 KB
english, 2006
7

On Worst‐Case to Average‐Case Reductions for NP Problems

Bogdanov, Andrej, Trevisan, Luca
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 372 KB
english, 2006
8

An Unconditional Study of Computational Zero Knowledge

Vadhan, Salil P.
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 501 KB
english, 2006
9

Derandomizing Homomorphism Testing in General Groups

Shpilka, Amir, Wigderson, Avi
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 202 KB
english, 2006
10

Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem

Dinur, Irit, Reingold, Omer
Journal:
SIAM Journal on Computing
Year:
2006
Language:
english
File:
PDF, 579 KB
english, 2006