Eli Ben-Sasson

	2012
92		Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer: On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs. Electronic Colloquium on Computational Complexity (ECCC) 19: 45 (2012)
91		Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan: Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC) 19: 49 (2012)
90		Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer: Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems. IACR Cryptology ePrint Archive 2012: 71 (2012)
	2011
89		Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan: On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM 2011: 400-411
88		Eli Ben-Sasson, Madhu Sudan: Limits on the Rate of Locally Testable Affine-Invariant Codes. APPROX-RANDOM 2011: 412-423
87		Eli Ben-Sasson, Jakob Nordström: Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. ICS 2011: 401-416
86		Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC Codes are not Necessarily Locally Testable. IEEE Conference on Computational Complexity 2011: 55-65
85		Eli Ben-Sasson, Michael Viderman: Towards Lower Bounds on Locally Testable Codes via Density Arguments. IEEE Conference on Computational Complexity 2011: 66-76
84		Eli Ben-Sasson, Jan Johannsen: Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width. IJCAI 2011: 2570-2575
83		Noga Zewi, Eli Ben-Sasson: From affine to two-source extractors via approximate duality. STOC 2011: 177-186
82		Eli Ben-Sasson, Shachar Lovett, Noga Zewi: An additive combinatorics approach to the log-rank conjecture in communication complexity CoRR abs/1111.5884: (2011)
81		Eli Ben-Sasson, Ariel Gabizon: Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic. Electronic Colloquium on Computational Complexity (ECCC) 18: 129 (2011)
80		Eli Ben-Sasson, Shachar Lovett, Noga Zewi: An additive combinatorics approach to the log-rank conjecture in communication complexity. Electronic Colloquium on Computational Complexity (ECCC) 18: 157 (2011)
79		Eli Ben-Sasson, Michael Viderman: Composition of semi-LTCs by two-wise Tensor Products. Electronic Colloquium on Computational Complexity (ECCC) 18: 70 (2011)
78		Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan: On Sums of Locally Testable Affine Invariant Properties. Electronic Colloquium on Computational Complexity (ECCC) 18: 79 (2011)
77		Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky: Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority. IACR Cryptology ePrint Archive 2011: 629 (2011)
	2010
76		Eli Ben-Sasson, Michael Viderman: Low Rate Is Insufficient for Local Testability. APPROX-RANDOM 2010: 420-433
75		Eli Ben-Sasson: Limitation on the Rate of Families of Locally Testable Codes. Property Testing 2010: 13-31
74		Eli Ben-Sasson, Jan Johannsen: Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas. SAT 2010: 16-29
73		Eli Ben-Sasson, Prahladh Harsha: Lower bounds for bounded depth Frege proofs via Pudlák-Buss games. ACM Trans. Comput. Log. 11(3): (2010)
72		Eli Ben-Sasson, Jakob Nordström: Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions CoRR abs/1008.1789: (2010)
71		Eli Ben-Sasson, Russell Impagliazzo: Random Cnf's are Hard for the Polynomial Calculus. Computational Complexity 19(4): 501-519 (2010)
70		Eli Ben-Sasson, Madhu Sudan: Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 108 (2010)
69		Eli Ben-Sasson: Limitation on the rate of families of locally testable codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 123 (2010)
68		Eli Ben-Sasson, Jakob Nordström: Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. Electronic Colloquium on Computational Complexity (ECCC) 17: 125 (2010)
67		Eli Ben-Sasson, Noga Zewi: From Affine to Two-Source Extractors via Approximate Duality. Electronic Colloquium on Computational Complexity (ECCC) 17: 144 (2010)
66		Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC codes are not necessarily locally testable. Electronic Colloquium on Computational Complexity (ECCC) 17: 199 (2010)
65		Eli Ben-Sasson, Michael Viderman: Towards lower bounds on locally testable codes via density arguments. Electronic Colloquium on Computational Complexity (ECCC) 17: 200 (2010)
64		Eli Ben-Sasson, Michael Viderman: Low Rate Is Insufficient for Local Testability. Electronic Colloquium on Computational Complexity (ECCC) 17: 4 (2010)
63		Eli Ben-Sasson, Swastik Kopparty: Affine Dispersers from Subspace Polynomials. Electronic Colloquium on Computational Complexity (ECCC) 17: 44 (2010)
62		Shir Ben-Israel, Eli Ben-Sasson, David R. Karger: Breaking local symmetries can dramatically reduce the length of propositional refutations. Electronic Colloquium on Computational Complexity (ECCC) 17: 68 (2010)
61		Eli Ben-Sasson, Jan Johannsen: Lower bounds for width-restricted clause learning on small width formulas. Electronic Colloquium on Computational Complexity (ECCC) 17: 85 (2010)
60		Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan: Subspace polynomials and limits to list decoding of Reed-Solomon codes. IEEE Transactions on Information Theory 56(1): 113-120 (2010)
59		Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. SIAM J. Comput. 39(7): 3230-3247 (2010)
	2009
58		Eli Ben-Sasson, Michael Viderman: Composition of Semi-LTCs by Two-Wise Tensor Products. APPROX-RANDOM 2009: 378-391
57		Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. IEEE Conference on Computational Complexity 2009: 52-61
56		Eli Ben-Sasson, Swastik Kopparty: Affine dispersers from subspace polynomials. STOC 2009: 65-74
55		Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. Electronic Colloquium on Computational Complexity (ECCC) 16: 126 (2009)
54		Eli Ben-Sasson, Jakob Nordström: Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. Electronic Colloquium on Computational Complexity (ECCC) 16: 2 (2009)
53		Eli Ben-Sasson, Jakob Nordström: Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs. Electronic Colloquium on Computational Complexity (ECCC) 16: 34 (2009)
52		Eli Ben-Sasson, Jakob Nordström: A Space Hierarchy for k-DNF Resolution. Electronic Colloquium on Computational Complexity (ECCC) 16: 47 (2009)
51		Eli Ben-Sasson, Michael Viderman: Tensor Products of Weakly Smooth Codes are Robust. Electronic Colloquium on Computational Complexity (ECCC) 16: 7 (2009)
50		Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah: Sound 3-Query PCPPs Are Long. TOCT 1(2): (2009)
49		Eli Ben-Sasson, Michael Viderman: Tensor Products of Weakly Smooth Codes are Robust. Theory of Computing 5(1): 239-255 (2009)
	2008
48		Eli Ben-Sasson, Michael Viderman: Tensor Products of Weakly Smooth Codes Are Robust. APPROX-RANDOM 2008: 290-302
47		Eli Ben-Sasson, Jakob Nordström: Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. FOCS 2008: 709-718
46		Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah: Sound 3-Query PCPPs Are Long. ICALP (1) 2008: 686-697
45		Eli Ben-Sasson, Madhu Sudan: Short PCPs with Polylog Query Complexity. SIAM J. Comput. 38(2): 551-607 (2008)
	2007
44		Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish: Sound 3-query PCPPs are Long. Electronic Colloquium on Computational Complexity (ECCC) 14(127): (2007)
43		Mikhail Alekhnovich, Eli Ben-Sasson: Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs. SIAM J. Comput. 36(5): 1248-1263 (2007)
	2006
42		Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan: Subspace Polynomials and List Decoding of Reed-Solomon Codes. FOCS 2006: 207-216
41		Eli Ben-Sasson, Adam Tauman Kalai, Ehud Kalai: An Approach to Bounded Rationality. NIPS 2006: 145-152
40		Eli Ben-Sasson, Madhu Sudan: Robust locally testable codes and products of codes. Random Struct. Algorithms 28(4): 387-402 (2006)
39		Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. 36(4): 889-974 (2006)
	2005
38		Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Short PCPs Verifiable in Polylogarithmic Time. IEEE Conference on Computational Complexity 2005: 120-134
37		Eli Ben-Sasson, Madhu Sudan: Simple PCPs with poly-log rate and query complexity. STOC 2005: 266-275
36		Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova: Some 3CNF Properties Are Hard to Test. SIAM J. Comput. 35(1): 1-21 (2005)
	2004
35		Eli Ben-Sasson, Madhu Sudan: Robust Locally Testable Codes and Products of Codes. APPROX-RANDOM 2004: 286-297
34		Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust pcps of proximity, shorter pcps and applications to coding. STOC 2004: 1-10
33		Eli Ben-Sasson, Madhu Sudan: Robust Locally Testable Codes and Products of Codes CoRR cs.IT/0408066: (2004)
32		Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near Optimal Separation Of Tree-Like And General Resolution. Combinatorica 24(4): 585-603 (2004)
31		Michael Alekhnovich, Eli Ben-Sasson: Linear Upper Bounds for Random Walk on Small Density Random 3CNFs Electronic Colloquium on Computational Complexity (ECCC)(016): (2004)
30		Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust PCPs of Proximity, Shorter PCPs and Applications to Coding Electronic Colloquium on Computational Complexity (ECCC)(021): (2004)
29		Eli Ben-Sasson, Madhu Sudan: Robust Locally Testable Codes and Products of Codes Electronic Colloquium on Computational Complexity (ECCC)(046): (2004)
28		Eli Ben-Sasson, Madhu Sudan: Simple PCPs with Poly-log Rate and Query Complexity Electronic Colloquium on Computational Complexity (ECCC)(060): (2004)
27		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34(1): 67-88 (2004)
	2003
26		Michael Alekhnovich, Eli Ben-Sasson: Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. FOCS 2003: 352-361
25		Eli Ben-Sasson, Oded Goldreich, Madhu Sudan: Bounds on 2-Query Codeword Testing. RANDOM-APPROX 2003: 216-227
24		Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova: Some 3CNF properties are hard to test. STOC 2003: 345-354
23		Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC 2003: 612-621
22		Eli Ben-Sasson, Prahladh Harsha: Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games Electronic Colloquium on Computational Complexity (ECCC) 10(004): (2003)
21		Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova: 3CNF Properties are Hard to Test Electronic Colloquium on Computational Complexity (ECCC) 10(006): (2003)
20		Eli Ben-Sasson, Oded Goldreich, Madhu Sudan: Bounds on 2-Query Codeword Testing. Electronic Colloquium on Computational Complexity (ECCC) 10(019): (2003)
19		Eli Ben-Sasson, Nicola Galesi: Space complexity of random formulae in resolution. Random Struct. Algorithms 23(1): 92-109 (2003)
	2002
18		Eli Ben-Sasson: Hard Examples for Bounded Depth Frege. IEEE Conference on Computational Complexity 2002: 4
17		Eli Ben-Sasson: Size space tradeoffs for resolution. STOC 2002: 457-464
16		Eli Ben-Sasson: Hard examples for bounded depth frege. STOC 2002: 563-572
15		Eli Ben-Sasson: Hard examples for the bounded depth Frege proof system. Computational Complexity 11(3-4): 109-136 (2002)
14		Eli Ben-Sasson, Yonatan Bilu: A Gap in Average Proof Complexity Electronic Colloquium on Computational Complexity (ECCC)(003): (2002)
13		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus. SIAM J. Comput. 31(4): 1184-1211 (2002)
	2001
12		Eli Ben-Sasson, Nicola Galesi: Space Complexity of Random Formulae in Resolution. IEEE Conference on Computational Complexity 2001: 42-51
11		Eli Ben-Sasson, Nicola Galesi: Space Complexity of Random Formulae in Resolution Electronic Colloquium on Computational Complexity (ECCC) 8(31): (2001)
10		Eli Ben-Sasson, Avi Wigderson: Short proofs are narrow - resolution made simple. J. ACM 48(2): 149-169 (2001)
	2000
9		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53
8		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367
7		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity Electronic Colloquium on Computational Complexity (ECCC) 7(23): (2000)
6		Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson: Near-Optimal Separation of Treelike and General Resolution Electronic Colloquium on Computational Complexity (ECCC) 7(5): (2000)
	1999
5		Eli Ben-Sasson, Russell Impagliazzo: Random CNF's are Hard for the Polynomial Calculus. FOCS 1999: 415-421
4		Eli Ben-Sasson, Avi Wigderson: Short Proofs Are Narrow - Resolution Made Simple (Abstract). IEEE Conference on Computational Complexity 1999: 2
3		Eli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution Made Simple. STOC 1999: 517-526
2		Eli Ben-Sasson, Avi Wigderson: Short Proofs are Narrow - Resolution made Simple Electronic Colloquium on Computational Complexity (ECCC) 6(22): (1999)
1		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus Electronic Colloquium on Computational Complexity (ECCC)(40): (1999)

Coauthor Index

1	Michael Alekhnovich	[1] [7] [8] [9] [13] [26] [27] [31]
2	Mikhail Alekhnovich	[43]
3	Shir Ben-Israel	[62]
4	Yonatan Bilu	[14]
5	Alessandro Chiesa	[90] [92]
6	Serge Fehr	[77]
7	Ariel Gabizon	[81]
8	Nicola Galesi	[11] [12] [19]
9	Daniel Genkin	[90] [92]
10	Oded Goldreich	[20] [25] [30] [34] [38] [39]
11	Elena Grigorescu	[78] [89]
12	Venkatesan Guruswami	[55] [57] [59]
13	Prahladh Harsha	[21] [22] [24] [30] [34] [36] [38] [39] [44] [46] [50] [73]
14	Russell Impagliazzo	[5] [6] [32] [71]
15	Jan Johannsen	[61] [74] [84]
16	Adam Tauman Kalai (Adam Kalai)	[41]
17	Ehud Kalai	[41]
18	David R. Karger	[62]
19	Tali Kaufman	[55] [57] [59]
20	Swastik Kopparty	[42] [56] [60] [63]
21	Oded Lachish	[44] [46] [50]
22	Shachar Lovett	[80] [82]
23	Ghid Maatouk	[66] [78] [86] [89]
24	Arie Matsliah	[44] [46] [50]
25	Jakob Nordström	[47] [52] [53] [54] [68] [72] [87]
26	Rafail Ostrovsky	[77]
27	Jaikumar Radhakrishnan	[42] [60]
28	Sofya Raskhodnikova	[21] [24] [36]
29	Alexander A. Razborov	[1] [7] [8] [9] [13] [27]
30	Noga Ron-Zewi	[91]
31	Amir Shpilka	[66] [78] [86] [89]
32	Madhu Sudan	[20] [23] [25] [28] [29] [30] [33] [34] [35] [37] [38] [39] [40] [45] [55] [57] [59] [66] [70] [78] [86] [88] [89] [91]
33	Eran Tromer	[90] [92]
34	Salil P. Vadhan	[23] [30] [34] [38] [39]
35	Michael Viderman	[48] [49] [51] [55] [57] [58] [59] [64] [65] [76] [79] [85]
36	Avi Wigderson	[1] [2] [3] [4] [6] [7] [8] [9] [10] [13] [23] [27] [32]
37	Noga Zewi	[67] [80] [82] [83]

Colors in the list of coauthors

Last update Sun May 27 04:04:01 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page