2009 |
111 | EE | Ran Raz:
Multi-linear formulas for permanent and determinant are of super-polynomial size.
J. ACM 56(2): (2009) |
2008 |
110 | EE | Ran Raz,
Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
FOCS 2008: 273-282 |
109 | EE | Dana Moshkovitz,
Ran Raz:
Two Query PCP with Sub-Constant Error.
FOCS 2008: 314-323 |
108 | EE | Ran Raz:
A Counterexample to Strong Parallel Repetition.
FOCS 2008: 369-373 |
107 | EE | Yael Tauman Kalai,
Ran Raz:
Interactive PCP.
ICALP (2) 2008: 536-547 |
106 | EE | Ran Raz,
Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
IEEE Conference on Computational Complexity 2008: 128-139 |
105 | EE | Ran Raz:
Elusive functions and lower bounds for arithmetic circuits.
STOC 2008: 711-720 |
104 | EE | Ran Raz,
Iddo Tzameret:
Resolution over linear equations and multilinear proofs.
Ann. Pure Appl. Logic 155(3): 194-224 (2008) |
103 | EE | Ariel Gabizon,
Ran Raz:
Deterministic extractors for affine sources over large fields.
Combinatorica 28(4): 415-440 (2008) |
102 | EE | Ran Raz,
Iddo Tzameret:
The Strength of Multilinear Proofs.
Computational Complexity 17(3): 407-457 (2008) |
101 | EE | Ran Raz:
Elusive Functions and Lower Bounds for Arithmetic Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 15(001): (2008) |
100 | EE | Ran Raz,
Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 15(006): (2008) |
99 | EE | Ran Raz:
A Counterexample to Strong Parallel Repetition.
Electronic Colloquium on Computational Complexity (ECCC) 15(018): (2008) |
98 | EE | Dana Moshkovitz,
Ran Raz:
Two Query PCP with Sub-Constant Error.
Electronic Colloquium on Computational Complexity (ECCC) 15(070): (2008) |
97 | EE | Dana Moshkovitz,
Ran Raz:
Two Query PCP with Sub-Constant Error.
Electronic Colloquium on Computational Complexity (ECCC) 15(071): (2008) |
96 | EE | Zeev Dvir,
Ran Raz:
Analyzing linear mergers.
Random Struct. Algorithms 32(3): 334-345 (2008) |
95 | EE | Dana Moshkovitz,
Ran Raz:
Sub-Constant Error Low Degree Test of Almost-Linear Size.
SIAM J. Comput. 38(1): 140-180 (2008) |
94 | EE | Ran Raz,
Amir Shpilka,
Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
SIAM J. Comput. 38(4): 1624-1647 (2008) |
93 | EE | Dmitry Gavinsky,
Julia Kempe,
Iordanis Kerenidis,
Ran Raz,
Ronald de Wolf:
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography.
SIAM J. Comput. 38(5): 1695-1708 (2008) |
2007 |
92 | EE | Ran Raz,
Amir Shpilka,
Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
FOCS 2007: 438-448 |
91 | EE | Dmitry Gavinsky,
Julia Kempe,
Iordanis Kerenidis,
Ran Raz,
Ronald de Wolf:
Exponential separations for one-way quantum communication complexity, with applications to cryptography.
STOC 2007: 516-525 |
90 | EE | Ran Raz,
Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs
CoRR abs/0708.1529: (2007) |
89 | EE | Dana Moshkovitz,
Ran Raz:
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size.
Electronic Colloquium on Computational Complexity (ECCC) 14(026): (2007) |
88 | EE | Yael Tauman Kalai,
Ran Raz:
Interactive PCP.
Electronic Colloquium on Computational Complexity (ECCC) 14(031): (2007) |
87 | EE | Ran Raz,
Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs.
Electronic Colloquium on Computational Complexity (ECCC) 14(078): (2007) |
86 | EE | Ran Raz,
Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
Electronic Colloquium on Computational Complexity (ECCC) 14(085): (2007) |
2006 |
85 | EE | Yael Tauman Kalai,
Ran Raz:
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP.
FOCS 2006: 355-366 |
84 | EE | Dana Moshkovitz,
Ran Raz:
Sub-constant error low degree test of almost-linear size.
STOC 2006: 21-30 |
83 | EE | Iordanis Kerenidis,
Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem
CoRR abs/quant-ph/0607173: (2006) |
82 | EE | Ran Raz,
Iddo Tzameret:
The Strength of Multilinear Proofs
Electronic Colloquium on Computational Complexity (ECCC)(001): (2006) |
81 | EE | Ran Raz,
Amir Shpilka,
Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 13(060): (2006) |
80 | EE | Iordanis Kerenidis,
Ran Raz:
The one-way communication complexity of the Boolean Hidden Matching Problem.
Electronic Colloquium on Computational Complexity (ECCC) 13(087): (2006) |
79 | EE | Ariel Gabizon,
Ran Raz,
Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.
SIAM J. Comput. 36(4): 1072-1094 (2006) |
78 | EE | Ran Raz:
Separation of Multilinear Circuit and Formula Size.
Theory of Computing 2(1): 121-135 (2006) |
2005 |
77 | EE | Ariel Gabizon,
Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields.
FOCS 2005: 407-418 |
76 | EE | Ran Raz:
Quantum Information and the PCP Theorem.
FOCS 2005: 459-468 |
75 | EE | Ran Raz:
Extractors with weak random seeds.
STOC 2005: 11-20 |
74 | EE | Ran Raz,
Amir Shpilka:
Deterministic polynomial identity testing in non-commutative models.
Computational Complexity 14(1): 1-19 (2005) |
73 | EE | Zeev Dvir,
Ran Raz:
Analyzing Linear Mergers
Electronic Colloquium on Computational Complexity (ECCC)(025): (2005) |
72 | EE | Ran Raz:
Quantum Information and the PCP Theorem
Electronic Colloquium on Computational Complexity (ECCC)(038): (2005) |
71 | EE | Dana Moshkovitz,
Ran Raz:
Sub-Constant Error Low Degree Test of Almost Linear Size
Electronic Colloquium on Computational Complexity (ECCC)(086): (2005) |
70 | EE | Ariel Gabizon,
Ran Raz:
Deterministic Extractors for Affine Sources over Large Fields
Electronic Colloquium on Computational Complexity (ECCC)(108): (2005) |
69 | EE | Ariel Gabizon,
Ran Raz,
Ronen Shaltiel:
Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed
Electronic Colloquium on Computational Complexity (ECCC)(109): (2005) |
68 | EE | Dieter van Melkebeek,
Ran Raz:
A time lower bound for satisfiability.
Theor. Comput. Sci. 348(2-3): 311-320 (2005) |
2004 |
67 | EE | Yevgeniy Dodis,
Ariel Elbaz,
Roberto Oliveira,
Ran Raz:
Improved Randomness Extraction from Two Independent Sources.
APPROX-RANDOM 2004: 334-344 |
66 | EE | Ran Raz:
Multilinear-NC neq Multilinear-NC.
FOCS 2004: 344-351 |
65 | EE | Ariel Gabizon,
Ran Raz,
Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.
FOCS 2004: 394-403 |
64 | EE | Dieter van Melkebeek,
Ran Raz:
A Time Lower Bound for Satisfiability.
ICALP 2004: 971-982 |
63 | EE | Ran Raz,
Amir Shpilka:
Deterministic Polynomial Identity Testing in Non-Commutative Models.
IEEE Conference on Computational Complexity 2004: 215-222 |
62 | EE | Ran Raz,
Amir Shpilka:
On the Power of Quantum Proofs.
IEEE Conference on Computational Complexity 2004: 260-274 |
61 | EE | Ran Raz:
Multi-linear formulas for permanent and determinant are of super-polynomial size.
STOC 2004: 633-641 |
60 | EE | Toniann Pitassi,
Ran Raz:
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.
Combinatorica 24(3): 503-524 (2004) |
59 | EE | Ran Raz:
Multilinear-NC1 != Multilinear-NC2
Electronic Colloquium on Computational Complexity (ECCC)(042): (2004) |
58 | EE | Ran Raz:
Extractors with Weak Random Seeds
Electronic Colloquium on Computational Complexity (ECCC)(099): (2004) |
57 | EE | Ran Raz:
Resolution lower bounds for the weak pigeonhole principle.
J. ACM 51(2): 115-138 (2004) |
56 | EE | Cyril Gavoille,
David Peleg,
Stéphane Pérennes,
Ran Raz:
Distance labeling in graphs.
J. Algorithms 53(1): 85-112 (2004) |
55 | EE | Joshua Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
SIAM J. Comput. 34(2): 261-276 (2004) |
2003 |
54 | EE | Ran Raz:
P != NP, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle
CoRR cs.CC/0304041: (2003) |
53 | EE | Irit Dinur,
Guy Kindler,
Ran Raz,
Shmuel Safra:
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.
Combinatorica 23(2): 205-243 (2003) |
52 | EE | Ran Raz:
Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size
Electronic Colloquium on Computational Complexity (ECCC)(067): (2003) |
51 | EE | Tzvika Hartman,
Ran Raz:
On the distribution of the number of roots of polynomials and explicit weak designs.
Random Struct. Algorithms 23(3): 235-263 (2003) |
50 | EE | Ran Raz,
Amir Shpilka:
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates.
SIAM J. Comput. 32(2): 488-513 (2003) |
49 | EE | Ran Raz:
On the Complexity of Matrix Product.
SIAM J. Comput. 32(5): 1356-1369 (2003) |
2002 |
48 | EE | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
FOCS 2002: 583-592 |
47 | EE | Ran Raz:
Resolution Lower Bounds for the Weak Pigeonhole Principle.
IEEE Conference on Computational Complexity 2002: 3 |
46 | EE | Ran Raz:
On the complexity of matrix product.
STOC 2002: 144-151 |
45 | EE | Ran Raz:
Resolution lower bounds for the weak pigeonhole principle.
STOC 2002: 553-562 |
44 | EE | Ran Raz:
On the Complexity of Matrix Product
Electronic Colloquium on Computational Complexity (ECCC)(012): (2002) |
43 | EE | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium on Computational Complexity (ECCC)(023): (2002) |
42 | EE | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
J. Comput. Syst. Sci. 65(1): 97-128 (2002) |
2001 |
41 | EE | Cyril Gavoille,
David Peleg,
Stephane Perennes,
Ran Raz:
Distance labeling in graphs.
SODA 2001: 210-219 |
40 | EE | Toniann Pitassi,
Ran Raz:
Regular resolution lower bounds for the weak pigeonhole principle.
STOC 2001: 347-355 |
39 | EE | Oded Lachish,
Ran Raz:
Explicit lower bound of 4.5n - o(n) for boolena circuits.
STOC 2001: 399-408 |
38 | EE | Ran Raz,
Amir Shpilka:
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates.
STOC 2001: 409-418 |
37 | EE | Ran Raz:
Resolution Lower Bounds for the Weak Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC) 8(21): (2001) |
2000 |
36 | | Tzvika Hartman,
Ran Raz:
On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors.
ICALP Satellite Workshops 2000: 3-22 |
35 | EE | Danny Harnik,
Ran Raz:
Higher lower bounds on monotone size.
STOC 2000: 378-387 |
34 | EE | Ran Raz:
VC-Dimension of Sets of Permutations.
Combinatorica 20(2): 241-255 (2000) |
33 | EE | Ran Raz:
The BNS-Chung criterion for multi-party communication complexity.
Computational Complexity 9(2): 113-122 (2000) |
32 | EE | Ran Raz,
Amir Shpilka:
Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates
Electronic Colloquium on Computational Complexity (ECCC) 7(29): (2000) |
31 | EE | Tzvika Hartman,
Ran Raz:
On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors
Electronic Colloquium on Computational Complexity (ECCC) 7(44): (2000) |
30 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
On Interpolation and Automatization for Frege Systems.
SIAM J. Comput. 29(6): 1939-1967 (2000) |
1999 |
29 | EE | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Error Reduction for Extractors.
FOCS 1999: 191-201 |
28 | EE | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
STOC 1999: 149-158 |
27 | EE | Ran Raz,
Omer Reingold:
On Recycling the Randomness of States in Space Bounded Computation.
STOC 1999: 159-168 |
26 | EE | Irit Dinur,
Eldar Fischer,
Guy Kindler,
Ran Raz,
Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
STOC 1999: 29-40 |
25 | EE | Ran Raz:
Exponential Separation of Quantum and Classical Communication Complexity.
STOC 1999: 358-367 |
24 | EE | Ran Raz,
Pierre McKenzie:
Separation of the Monotone NC Hierarchy.
Combinatorica 19(3): 403-435 (1999) |
23 | EE | Ran Raz,
Omer Reingold,
Salil P. Vadhan:
Extracting All the Randomness and Reducing the Error in Trevisan's Extractors
Electronic Colloquium on Computational Complexity (ECCC)(46): (1999) |
22 | | Ran Raz,
Gábor Tardos,
Oleg Verbitsky,
Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees.
J. Comput. Syst. Sci. 59(2): 346-372 (1999) |
1998 |
21 | EE | Ran Raz,
Gábor Tardos,
Oleg Verbitsky,
Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees.
IEEE Conference on Computational Complexity 1998: 58-67 |
20 | EE | Yuri Rabinovich,
Ran Raz:
Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs.
Discrete & Computational Geometry 19(1): 79-94 (1998) |
19 | EE | Irit Dinur,
Eldar Fischer,
Guy Kindler,
Ran Raz,
Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Electronic Colloquium on Computational Complexity (ECCC) 5(66): (1998) |
18 | | Ran Raz:
A Parallel Repetition Theorem.
SIAM J. Comput. 27(3): 763-803 (1998) |
1997 |
17 | EE | Ran Raz,
Pierre McKenzie:
Separation of the Monotone NC Hierarchy.
FOCS 1997: 234-243 |
16 | EE | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
No Feasible Interpolation for TC0-Frege Proofs.
FOCS 1997: 254-263 |
15 | EE | Itzhak Parnafes,
Ran Raz,
Avi Wigderson:
Direct Product Results and the GCD Problem, in Old and New Communication Models.
STOC 1997: 363-372 |
14 | EE | Ran Raz,
Shmuel Safra:
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.
STOC 1997: 475-484 |
13 | EE | Ran Raz,
Gábor Tardos,
Oleg Verbitsky,
Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees
Electronic Colloquium on Computational Complexity (ECCC) 4(54): (1997) |
12 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
Lower Bounds for Cutting Planes Proofs with Small Coefficients.
J. Symb. Log. 62(3): 708-728 (1997) |
1995 |
11 | EE | Ran Raz:
A parallel repetition theorem.
STOC 1995: 447-456 |
10 | EE | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
Lower bounds for cutting planes proofs with small coefficients.
STOC 1995: 575-584 |
9 | | Ran Raz,
Boris Spieker:
On the ``Log Rank''-Conjecture in Communication Complexity.
Combinatorica 15(4): 567-588 (1995) |
8 | | Mauricio Karchmer,
Ran Raz,
Avi Wigderson:
Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity.
Computational Complexity 5(3/4): 191-204 (1995) |
7 | | Ran Raz:
Fourier Analysis for Probabilistic Communication Complexity.
Computational Complexity 5(3/4): 205-221 (1995) |
1994 |
6 | | Russell Impagliazzo,
Ran Raz,
Avi Wigderson:
A Direct Product Theorem.
Structure in Complexity Theory Conference 1994: 88-96 |
1993 |
5 | | Ran Raz,
Boris Spieker:
On the ``log rank''-Conjecture in Communication Complexity
FOCS 1993: 168-176 |
1992 |
4 | EE | Ran Raz,
Avi Wigderson:
Monotone Circuits for Matching Require Linear Depth.
J. ACM 39(3): 736-744 (1992) |
1991 |
3 | | Mauricio Karchmer,
Ran Raz,
Avi Wigderson:
Super-logarithmic Depth Lower Bounds via Direct Sum in Communication Coplexity.
Structure in Complexity Theory Conference 1991: 299-304 |
1990 |
2 | | Ran Raz,
Avi Wigderson:
Monotone Circuits for Matching Require Linear Depth
STOC 1990: 287-292 |
1989 |
1 | | Ran Raz,
Avi Wigderson:
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)
FOCS 1989: 562-567 |