Result 1 to 20 of 156 total
PCP characterizations of NP: toward a polynomially-small error-probability. (English)
Comput. Complexity 20, No. 3, 413-504 (2011).
1
A counterexample to strong parallel repetition. (English)
SIAM J. Comput. 40, No. 3, 771-777 (2011).
2
Memory delegation. (English)
Rogaway, Phillip (ed.), Advances in cryptology ‒ CRYPTO 2011. 31st annual cryptology conference, Santa Barbara, CA, USA, August 14‒18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22791-2/pbk). Lecture Notes in Computer Science 6841, 151-168 (2011).
3
Non-malleable extractors with short seeds and applications to privacy amplification. (English)
Electron. Colloq. Comput. Complex. 18, 96 (2011).
4
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. (English)
J. Comput. Syst. Sci. 77, No. 1, 167-190 (2011).
5
Memory delegation (English)
IACR Cryptology ePrint Archive 2011, 273 (2011).
6
Memory delegation (English)
CRYPTO, 151-168 (2011).
7
Elusive functions and lower bounds for arithmetic circuits. (English)
Theory Comput. 6, Paper No. 7, 135-177, electronic only (2010).
8
Sub-constant error probabilistically checkable proof of almost-linear size. (English)
Comput. Complexity 19, No. 3, 367-422 (2010).
9
Two-query PCP with subconstant error. (English)
J. ACM 57, No. 5 (2010).
10
Elusive functions and lower bounds for arithmetic circuits (English)
Theory of Computing 6, No. 1, 135-177 (2010).
11
Pseudorandom generators for regular branching programs (English)
FOCS, 40-47 (2010).
12
Parallel repetition of two prover games (Invited survey) (English)
IEEE Conference on Computational Complexity, 3-6 (2010).
13
Tensor-rank and lower bounds for arithmetic formulas (English)
STOC, 659-666 (2010).
14
Lower bounds and separations for constant depth multilinear circuits. (English)
Comput. Complexity 18, No. 2, 171-207 (2009).
15
Multi-linear formulas for permanent and determinant are of super-polynomial size. (English)
J. ACM 56, No. 2 (2009).
16
Strong parallel repetition theorem for free projection games. (English)
Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21‒23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 352-365 (2009).
17
Probabilistically checkable arguments. (English)
Halevi, Shai (ed.), Advances in cryptology ‒ CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16‒20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03355-1/pbk). Lecture Notes in Computer Science 5677, 143-159 (2009).
18
Quantum information and the PCP theorem. (English)
Algorithmica 55, No. 3, 462-489 (2009).
19
Probabilistically checkable arguments (English)
CRYPTO, 143-159 (2009).
20
Result 1 to 20 of 156 total
Start
Contact
Print
General Help
