×
Compute Distance To:
Author ID: raz.ran Recent zbMATH articles by "Raz, Ran"
Published as: Raz, Ran; Raz, R.

Publications by Year

Citations contained in zbMATH Open

96 Publications have been cited 1,224 times in 927 Documents Cited by Year
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Zbl 0963.68175
Raz, Ran; Safra, Shmuel
197
1999
A parallel repetition theorem. Zbl 0911.68082
Raz, Ran
107
1998
Distance labeling in graphs. Zbl 1068.68104
Gavoille, Cyril; Peleg, David; Pérennes, Stéphane; Raz, Ran
41
2004
Approximating CVP to within almost-polynomial factors is NP-hard. Zbl 1049.68072
Dinur, I.; Kindler, G.; Raz, R.; Safra, S.
29
2003
On interpolation and automatization for Frege systems. Zbl 0959.03044
Bonet, Maria Luisa; Pitassi, Toniann; Raz, Ran
28
2000
Separation of the monotone NC hierarchy. Zbl 0977.68037
Raz, Ran; McKenzie, Pierre
27
1999
Lower bounds and separations for constant depth multilinear circuits. Zbl 1213.68319
Raz, Ran; Yehudayoff, Amir
26
2009
Extractors with weak random seeds. Zbl 1192.68373
Raz, Ran
26
2005
Deterministic polynomial identity testing in non-commutative models. Zbl 1096.68070
Raz, Ran; Shpilka, Amir
25
2005
Two-query PCP with subconstant error. Zbl 1327.68110
Moshkovitz, Dana; Raz, Ran
25
2010
Monotone circuits for matching require linear depth. Zbl 0799.68077
Raz, Ran; Wigderson, Avi
24
1992
Multi-linear formulas for permanent and determinant are of super-polynomial size. Zbl 1325.68112
Raz, Ran
24
2009
Distance labeling in graphs (extended abstract). Zbl 0987.05083
Gavoille, Cyril; Peleg, David; Pérennes, Stéphane; Raz, Ran
23
2001
Lower bounds on the distortion of embedding finite metric spaces in graphs. Zbl 0890.05021
Rabinovich, Y.; Raz, R.
21
1998
Lower bounds for cutting planes proofs with small coefficients. Zbl 0889.03050
Bonet, Maria; Pitassi, Toniann; Raz, Ran
20
1997
How to delegate computations: the power of no-signaling proofs. Zbl 1315.68135
Kalai, Yael Tauman; Raz, Ran; Rothblum, Ron D.
20
2014
Super-logarithmic depth lower bounds via the direct sum in communication complexity. Zbl 0851.68034
Karchmer, Mauricio; Raz, Ran; Wigderson, Avi
18
1995
Memory delegation. Zbl 1288.68005
Chung, Kai-Min; Kalai, Yael Tauman; Liu, Feng-Hao; Raz, Ran
18
2011
Separation of multilinear circuit and formula size. Zbl 1213.68301
Raz, Ran
18
2006
Exponential separation of quantum and classical communication complexity. Zbl 1345.68134
Raz, Ran
18
1999
Explicit lower bound of \(4.5n-o(n)\) for Boolean circuits. Zbl 1323.68303
Lachish, Oded; Raz, Ran
18
2001
Deterministic extractors for bit-fixing sources by obtaining an independent seed. Zbl 1118.68096
Gabizon, Ariel; Raz, Ran; Shaltiel, Ronen
17
2006
Deterministic extractors for affine sources over large fields. Zbl 1174.05117
Gabizon, Ariel; Raz, Ran
17
2008
Balancing syntactically multilinear arithmetic circuits. Zbl 1188.68367
Raz, Ran; Yehudayoff, Amir
16
2008
Extracting all the randomness and reducing the error in Trevisan’s extractors. Zbl 1020.68029
Raz, Ran; Reingold, Omer; Vadhan, Salil
13
2002
Elusive functions and lower bounds for arithmetic circuits. Zbl 1213.68318
Raz, Ran
13
2010
On recycling the randomness of states in space bounded computation. Zbl 1345.68135
Raz, Ran; Reingold, Omer
13
1999
Improved randomness extraction from two independent sources. Zbl 1106.68036
Dodis, Yevgeniy; Elbaz, Ariel; Oliveira, Roberto; Raz, Ran
12
2004
Pseudorandom generators for regular branching programs. Zbl 1301.68192
Braverman, Mark; Rao, Anup; Raz, Ran; Yehudayoff, Amir
12
2014
A lower bound for the size of syntactically multilinear arithmetic circuits. Zbl 1192.68329
Raz, Ran; Shpilka, Amir; Yehudayoff, Amir
11
2008
Exponential separations for one-way quantum communication complexity, with applications to cryptography. Zbl 1232.68051
Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf; Ronald
11
2007
The surprise examination paradox and the second incompleteness theorem. Zbl 1261.03159
Kritchman, Shira; Raz, Ran
10
2010
Exponential separation for one-way quantum communication complexity, with applications to cryptography. Zbl 1175.81038
Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf, Ronald
10
2008
Interactive channel capacity. Zbl 1293.94047
Kol, Gillat; Raz, Ran
10
2013
Efficient multiparty protocols via log-depth threshold formulae. (Extended abstract). Zbl 1316.94066
Cohen, Gil; Damgård, Ivan Bjerre; Ishai, Yuval; Kölker, Jonas; Miltersen, Peter Bro; Raz, Ran; Rothblum, Ron D.
9
2013
Lower bounds for matrix product in bounded depth circuits with arbitrary gates. Zbl 1029.68072
Raz, Ran; Shpilka, Amir
9
2003
On the “log rank”-conjecture in communication complexity. Zbl 0845.68050
Raz, Ran; Spieker, Boris
9
1995
PCP characterizations of NP: toward a polynomially-small error-probability. Zbl 1234.68133
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
9
2011
Delegation for bounded space. Zbl 1293.68176
Tauman Kalai, Yael; Raz, Ran; Rothblum, Ron D.
9
2013
Exponential separation of communication and external information. Zbl 1377.68079
Ganor, Anat; Kol, Gillat; Raz, Ran
9
2016
The BNS-Chung criterion for multi-party communication complexity. Zbl 0971.68067
Raz, Ran
9
2000
On the complexity of matrix product. Zbl 1026.68060
Raz, Ran
8
2003
Fourier analysis for probabilistic communication complexity. Zbl 0851.68045
Raz, Ran
8
1995
A counterexample to strong parallel repetition. Zbl 1234.68141
Raz, Ran
8
2011
Elusive functions and lower bounds for arithmetic circuits. Zbl 1231.68143
Raz, Ran
8
2008
Resolution lower bounds for the weak pigeonhole principle. Zbl 1192.03043
Raz, Ran
8
2002
Multi-linear formulas for permanent and determinant are of super-polynomial size. Zbl 1192.68328
Raz, Ran
8
2004
Resolution lower bounds for the weak pigeonhole principle. Zbl 1317.03036
Raz, Ran
8
2004
Extracting all the randomness and reducing the error in Trevisan’s extractors. Zbl 1345.68136
Raz, Ran; Reingold, Omer; Vadhan, Salil
8
1999
Average-case lower bounds for formula size. Zbl 1293.68147
Komargodski, Ilan; Raz, Ran
8
2013
Tensor-rank and lower bounds for arithmetic formulas. Zbl 1293.90043
Raz, Ran
8
2010
Probabilistically checkable arguments. Zbl 1252.94079
Kalai, Yael Tauman; Raz, Ran
7
2009
Interactive PCP. Zbl 1155.68504
Kalai, Yael Tauman; Raz, Ran
7
2008
A parallel repetition theorem. Zbl 0978.68527
Raz, Ran
7
1995
Lower bounds for cutting planes proofs with small coefficients. Zbl 0925.03207
Bonet, Maria; Pitassi, Toniann; Raz, Ran
7
1995
On the complexity of matrix product. Zbl 1192.68327
Raz, Ran
7
2002
Arthur-Merlin streaming complexity. Zbl 1327.68101
Gur, Tom; Raz, Ran
7
2015
Exponential separation of information and communication for Boolean functions (extended abstract). Zbl 1321.68311
Ganor, Anat; Kol, Gillat; Raz, Ran
7
2015
Regular resolution lower bounds for the weak pigeonhole principle. Zbl 1323.03090
Pitassi, Toniann; Raz, Ran
7
2001
Resolution over linear equations and multilinear proofs. Zbl 1161.03034
Raz, Ran; Tzameret, Iddo
6
2008
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. Zbl 1209.68382
Raz, Ran; Yehudayoff, Amir
6
2011
Sub-constant error low degree test of almost-linear size. Zbl 1165.68029
Moshkovitz, Dana; Raz, Ran
6
2008
Tensor-rank and lower bounds for arithmetic formulas. Zbl 1281.68136
Raz, Ran
5
2013
Strong parallel repetition theorem for free projection games. Zbl 1255.68146
Barak, Boaz; Rao, Anup; Raz, Ran; Rosen, Ricky; Shaltiel, Ronen
5
2009
Higher lower bounds on monotone size. Zbl 1296.68069
Harnik, Danny; Raz, Ran
5
2000
Direct product results and the GCD problem, in old and new communication models. Zbl 0968.68070
Parnafes, Itzhak; Raz, Ran; Wigderson, Avi
5
1999
Quantum information and the PCP theorem. Zbl 1192.68280
Raz, Ran
4
2009
Sub-constant error probabilistically checkable proof of almost-linear size. Zbl 1213.68317
Moshkovitz, Dana; Raz, Ran
4
2010
Oracle separation of BQP and PH. Zbl 1433.68152
Raz, Ran; Tal, Avishay
4
2019
Sub-constant error low degree test of almost-linear size. Zbl 1301.68128
Moshkovitz, Dana; Raz, Ran
4
2006
PCP characterizations of NP: towards a polynomially-small error-probability. Zbl 1346.68096
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
4
1999
VC-dimension of sets of permutations. Zbl 0959.05001
Raz, Ran
4
2000
Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound. Zbl 1376.03043
Komargodski, Ilan; Raz, Ran; Tal, Avishay
4
2017
Bounds on locally testable codes with unique tests. Zbl 1347.68169
Kol, Gillat; Raz, Ran
3
2012
The strength of multilinear proofs. Zbl 1174.03025
Raz, Ran; Tzameret, Iddo
3
2008
Competing provers protocols for circuit evaluation. Zbl 1361.68091
Kol, Gillat; Raz, Ran
3
2013
Nonmalleable extractors with short seeds and applications to privacy amplification. Zbl 1302.94040
Cohen, Gil; Raz, Ran; Segev, Gil
3
2014
Exponential separation of information and communication for Boolean functions. Zbl 1412.68082
Ganor, Anat; Kol, Gillat; Raz, Ran
3
2016
Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner. Zbl 1398.68392
Dinitz, Michael; Kortsarz, Guy; Raz, Ran
3
2016
Analyzing linear mergers. Zbl 1136.68623
Dvir, Zeev; Raz, Ran
2
2008
Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner. Zbl 1272.68153
Dinitz, Michael; Kortsarz, Guy; Raz, Ran
2
2012
On the distribution of the number of roots of polynomials and explicit weak designs. Zbl 1051.68149
Hartman, Tzvika; Raz, Ran
2
2003
Regular resolution lower bounds for the weak pigeonhole principle. Zbl 1063.03044
Pitassi, Toniann; Raz, Ran
2
2004
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. Zbl 1323.68306
Raz, Ran; Shpilka, Amir
2
2001
Extractor-based time-space lower bounds for learning. Zbl 1428.68238
Garg, Sumegha; Raz, Ran; Tal, Avishay
2
2018
Arthur-Merlin games in Boolean decision trees. Zbl 0946.68055
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshagin, Nikolai
1
1998
Fast learning requires good memory: a time-space lower bound for parity learning. Zbl 1426.68240
Raz, Ran
1
2019
Arthur-Merlin streaming complexity. Zbl 1327.68100
Gur, Tom; Raz, Ran
1
2013
Arthur-Merlin games in Boolean decision trees. Zbl 0945.68515
Raz, Ran; Verbitsky, Oleg; Tardos, Gábor; Vereshagin, Nikolai
1
1998
Arthur-Merlin games in Boolean decision trees. Zbl 0948.68166
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshchagin, Nikolai
1
1999
Bounds on 2-query locally testable codes with affine tests. Zbl 1357.68051
Kol, Gillat; Raz, Ran
1
2016
Time-space hardness of learning sparse parities. Zbl 1370.68132
Kol, Gillat; Raz, Ran; Tal, Avishay
1
2017
A time lower bound for satisfiability. Zbl 1090.68049
van Melkebeek, Dieter; Raz, Ran
1
2005
Two sides of the coin problem. Zbl 1360.68460
Cohen, Gil; Ganor, Anat; Raz, Ran
1
2014
Space pseudorandom generators by communication complexity lower bounds. Zbl 1359.68102
Ganor, Anat; Raz, Ran
1
2014
A candidate for a strong separation of information and communication. Zbl 1462.68054
Braverman, Mark; Ganor, Anat; Kol, Gillat; Raz, Ran
1
2018
Oracle separation of BQP and PH. Zbl 1433.68152
Raz, Ran; Tal, Avishay
4
2019
Fast learning requires good memory: a time-space lower bound for parity learning. Zbl 1426.68240
Raz, Ran
1
2019
Extractor-based time-space lower bounds for learning. Zbl 1428.68238
Garg, Sumegha; Raz, Ran; Tal, Avishay
2
2018
A candidate for a strong separation of information and communication. Zbl 1462.68054
Braverman, Mark; Ganor, Anat; Kol, Gillat; Raz, Ran
1
2018
Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound. Zbl 1376.03043
Komargodski, Ilan; Raz, Ran; Tal, Avishay
4
2017
Time-space hardness of learning sparse parities. Zbl 1370.68132
Kol, Gillat; Raz, Ran; Tal, Avishay
1
2017
Exponential separation of communication and external information. Zbl 1377.68079
Ganor, Anat; Kol, Gillat; Raz, Ran
9
2016
Exponential separation of information and communication for Boolean functions. Zbl 1412.68082
Ganor, Anat; Kol, Gillat; Raz, Ran
3
2016
Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner. Zbl 1398.68392
Dinitz, Michael; Kortsarz, Guy; Raz, Ran
3
2016
Bounds on 2-query locally testable codes with affine tests. Zbl 1357.68051
Kol, Gillat; Raz, Ran
1
2016
Arthur-Merlin streaming complexity. Zbl 1327.68101
Gur, Tom; Raz, Ran
7
2015
Exponential separation of information and communication for Boolean functions (extended abstract). Zbl 1321.68311
Ganor, Anat; Kol, Gillat; Raz, Ran
7
2015
How to delegate computations: the power of no-signaling proofs. Zbl 1315.68135
Kalai, Yael Tauman; Raz, Ran; Rothblum, Ron D.
20
2014
Pseudorandom generators for regular branching programs. Zbl 1301.68192
Braverman, Mark; Rao, Anup; Raz, Ran; Yehudayoff, Amir
12
2014
Nonmalleable extractors with short seeds and applications to privacy amplification. Zbl 1302.94040
Cohen, Gil; Raz, Ran; Segev, Gil
3
2014
Two sides of the coin problem. Zbl 1360.68460
Cohen, Gil; Ganor, Anat; Raz, Ran
1
2014
Space pseudorandom generators by communication complexity lower bounds. Zbl 1359.68102
Ganor, Anat; Raz, Ran
1
2014
Interactive channel capacity. Zbl 1293.94047
Kol, Gillat; Raz, Ran
10
2013
Efficient multiparty protocols via log-depth threshold formulae. (Extended abstract). Zbl 1316.94066
Cohen, Gil; Damgård, Ivan Bjerre; Ishai, Yuval; Kölker, Jonas; Miltersen, Peter Bro; Raz, Ran; Rothblum, Ron D.
9
2013
Delegation for bounded space. Zbl 1293.68176
Tauman Kalai, Yael; Raz, Ran; Rothblum, Ron D.
9
2013
Average-case lower bounds for formula size. Zbl 1293.68147
Komargodski, Ilan; Raz, Ran
8
2013
Tensor-rank and lower bounds for arithmetic formulas. Zbl 1281.68136
Raz, Ran
5
2013
Competing provers protocols for circuit evaluation. Zbl 1361.68091
Kol, Gillat; Raz, Ran
3
2013
Arthur-Merlin streaming complexity. Zbl 1327.68100
Gur, Tom; Raz, Ran
1
2013
Bounds on locally testable codes with unique tests. Zbl 1347.68169
Kol, Gillat; Raz, Ran
3
2012
Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner. Zbl 1272.68153
Dinitz, Michael; Kortsarz, Guy; Raz, Ran
2
2012
Memory delegation. Zbl 1288.68005
Chung, Kai-Min; Kalai, Yael Tauman; Liu, Feng-Hao; Raz, Ran
18
2011
PCP characterizations of NP: toward a polynomially-small error-probability. Zbl 1234.68133
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
9
2011
A counterexample to strong parallel repetition. Zbl 1234.68141
Raz, Ran
8
2011
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. Zbl 1209.68382
Raz, Ran; Yehudayoff, Amir
6
2011
Two-query PCP with subconstant error. Zbl 1327.68110
Moshkovitz, Dana; Raz, Ran
25
2010
Elusive functions and lower bounds for arithmetic circuits. Zbl 1213.68318
Raz, Ran
13
2010
The surprise examination paradox and the second incompleteness theorem. Zbl 1261.03159
Kritchman, Shira; Raz, Ran
10
2010
Tensor-rank and lower bounds for arithmetic formulas. Zbl 1293.90043
Raz, Ran
8
2010
Sub-constant error probabilistically checkable proof of almost-linear size. Zbl 1213.68317
Moshkovitz, Dana; Raz, Ran
4
2010
Lower bounds and separations for constant depth multilinear circuits. Zbl 1213.68319
Raz, Ran; Yehudayoff, Amir
26
2009
Multi-linear formulas for permanent and determinant are of super-polynomial size. Zbl 1325.68112
Raz, Ran
24
2009
Probabilistically checkable arguments. Zbl 1252.94079
Kalai, Yael Tauman; Raz, Ran
7
2009
Strong parallel repetition theorem for free projection games. Zbl 1255.68146
Barak, Boaz; Rao, Anup; Raz, Ran; Rosen, Ricky; Shaltiel, Ronen
5
2009
Quantum information and the PCP theorem. Zbl 1192.68280
Raz, Ran
4
2009
Deterministic extractors for affine sources over large fields. Zbl 1174.05117
Gabizon, Ariel; Raz, Ran
17
2008
Balancing syntactically multilinear arithmetic circuits. Zbl 1188.68367
Raz, Ran; Yehudayoff, Amir
16
2008
A lower bound for the size of syntactically multilinear arithmetic circuits. Zbl 1192.68329
Raz, Ran; Shpilka, Amir; Yehudayoff, Amir
11
2008
Exponential separation for one-way quantum communication complexity, with applications to cryptography. Zbl 1175.81038
Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf, Ronald
10
2008
Elusive functions and lower bounds for arithmetic circuits. Zbl 1231.68143
Raz, Ran
8
2008
Interactive PCP. Zbl 1155.68504
Kalai, Yael Tauman; Raz, Ran
7
2008
Resolution over linear equations and multilinear proofs. Zbl 1161.03034
Raz, Ran; Tzameret, Iddo
6
2008
Sub-constant error low degree test of almost-linear size. Zbl 1165.68029
Moshkovitz, Dana; Raz, Ran
6
2008
The strength of multilinear proofs. Zbl 1174.03025
Raz, Ran; Tzameret, Iddo
3
2008
Analyzing linear mergers. Zbl 1136.68623
Dvir, Zeev; Raz, Ran
2
2008
Exponential separations for one-way quantum communication complexity, with applications to cryptography. Zbl 1232.68051
Gavinsky, Dmitry; Kempe, Julia; Kerenidis, Iordanis; Raz, Ran; de Wolf; Ronald
11
2007
Separation of multilinear circuit and formula size. Zbl 1213.68301
Raz, Ran
18
2006
Deterministic extractors for bit-fixing sources by obtaining an independent seed. Zbl 1118.68096
Gabizon, Ariel; Raz, Ran; Shaltiel, Ronen
17
2006
Sub-constant error low degree test of almost-linear size. Zbl 1301.68128
Moshkovitz, Dana; Raz, Ran
4
2006
Extractors with weak random seeds. Zbl 1192.68373
Raz, Ran
26
2005
Deterministic polynomial identity testing in non-commutative models. Zbl 1096.68070
Raz, Ran; Shpilka, Amir
25
2005
A time lower bound for satisfiability. Zbl 1090.68049
van Melkebeek, Dieter; Raz, Ran
1
2005
Distance labeling in graphs. Zbl 1068.68104
Gavoille, Cyril; Peleg, David; Pérennes, Stéphane; Raz, Ran
41
2004
Improved randomness extraction from two independent sources. Zbl 1106.68036
Dodis, Yevgeniy; Elbaz, Ariel; Oliveira, Roberto; Raz, Ran
12
2004
Multi-linear formulas for permanent and determinant are of super-polynomial size. Zbl 1192.68328
Raz, Ran
8
2004
Resolution lower bounds for the weak pigeonhole principle. Zbl 1317.03036
Raz, Ran
8
2004
Regular resolution lower bounds for the weak pigeonhole principle. Zbl 1063.03044
Pitassi, Toniann; Raz, Ran
2
2004
Approximating CVP to within almost-polynomial factors is NP-hard. Zbl 1049.68072
Dinur, I.; Kindler, G.; Raz, R.; Safra, S.
29
2003
Lower bounds for matrix product in bounded depth circuits with arbitrary gates. Zbl 1029.68072
Raz, Ran; Shpilka, Amir
9
2003
On the complexity of matrix product. Zbl 1026.68060
Raz, Ran
8
2003
On the distribution of the number of roots of polynomials and explicit weak designs. Zbl 1051.68149
Hartman, Tzvika; Raz, Ran
2
2003
Extracting all the randomness and reducing the error in Trevisan’s extractors. Zbl 1020.68029
Raz, Ran; Reingold, Omer; Vadhan, Salil
13
2002
Resolution lower bounds for the weak pigeonhole principle. Zbl 1192.03043
Raz, Ran
8
2002
On the complexity of matrix product. Zbl 1192.68327
Raz, Ran
7
2002
Distance labeling in graphs (extended abstract). Zbl 0987.05083
Gavoille, Cyril; Peleg, David; Pérennes, Stéphane; Raz, Ran
23
2001
Explicit lower bound of \(4.5n-o(n)\) for Boolean circuits. Zbl 1323.68303
Lachish, Oded; Raz, Ran
18
2001
Regular resolution lower bounds for the weak pigeonhole principle. Zbl 1323.03090
Pitassi, Toniann; Raz, Ran
7
2001
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. Zbl 1323.68306
Raz, Ran; Shpilka, Amir
2
2001
On interpolation and automatization for Frege systems. Zbl 0959.03044
Bonet, Maria Luisa; Pitassi, Toniann; Raz, Ran
28
2000
The BNS-Chung criterion for multi-party communication complexity. Zbl 0971.68067
Raz, Ran
9
2000
Higher lower bounds on monotone size. Zbl 1296.68069
Harnik, Danny; Raz, Ran
5
2000
VC-dimension of sets of permutations. Zbl 0959.05001
Raz, Ran
4
2000
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. Zbl 0963.68175
Raz, Ran; Safra, Shmuel
197
1999
Separation of the monotone NC hierarchy. Zbl 0977.68037
Raz, Ran; McKenzie, Pierre
27
1999
Exponential separation of quantum and classical communication complexity. Zbl 1345.68134
Raz, Ran
18
1999
On recycling the randomness of states in space bounded computation. Zbl 1345.68135
Raz, Ran; Reingold, Omer
13
1999
Extracting all the randomness and reducing the error in Trevisan’s extractors. Zbl 1345.68136
Raz, Ran; Reingold, Omer; Vadhan, Salil
8
1999
Direct product results and the GCD problem, in old and new communication models. Zbl 0968.68070
Parnafes, Itzhak; Raz, Ran; Wigderson, Avi
5
1999
PCP characterizations of NP: towards a polynomially-small error-probability. Zbl 1346.68096
Dinur, Irit; Fischer, Eldar; Kindler, Guy; Raz, Ran; Safra, Shmuel
4
1999
Arthur-Merlin games in Boolean decision trees. Zbl 0948.68166
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshchagin, Nikolai
1
1999
A parallel repetition theorem. Zbl 0911.68082
Raz, Ran
107
1998
Lower bounds on the distortion of embedding finite metric spaces in graphs. Zbl 0890.05021
Rabinovich, Y.; Raz, R.
21
1998
Arthur-Merlin games in Boolean decision trees. Zbl 0946.68055
Raz, Ran; Tardos, Gábor; Verbitsky, Oleg; Vereshagin, Nikolai
1
1998
Arthur-Merlin games in Boolean decision trees. Zbl 0945.68515
Raz, Ran; Verbitsky, Oleg; Tardos, Gábor; Vereshagin, Nikolai
1
1998
Lower bounds for cutting planes proofs with small coefficients. Zbl 0889.03050
Bonet, Maria; Pitassi, Toniann; Raz, Ran
20
1997
Super-logarithmic depth lower bounds via the direct sum in communication complexity. Zbl 0851.68034
Karchmer, Mauricio; Raz, Ran; Wigderson, Avi
18
1995
On the “log rank”-conjecture in communication complexity. Zbl 0845.68050
Raz, Ran; Spieker, Boris
9
1995
Fourier analysis for probabilistic communication complexity. Zbl 0851.68045
Raz, Ran
8
1995
A parallel repetition theorem. Zbl 0978.68527
Raz, Ran
7
1995
Lower bounds for cutting planes proofs with small coefficients. Zbl 0925.03207
Bonet, Maria; Pitassi, Toniann; Raz, Ran
7
1995
Monotone circuits for matching require linear depth. Zbl 0799.68077
Raz, Ran; Wigderson, Avi
24
1992
all top 5

Cited by 1,395 Authors

15 Kortsarz, Guy
15 Raz, Ran
13 Pitassi, Toniann
12 Braverman, Mark
12 Dinur, Irit
11 Shaltiel, Ronen
11 Wigderson, Avi
10 Meir, Or
10 Yukna, Stasys P.
9 Göös, Mika
9 Håstad, Johan Torkel
9 Mahajan, Meena
9 Pelc, Andrzej
9 Peleg, David
9 Shpilka, Amir
8 Atserias, Albert
8 Chiesa, Alessandro
8 Guruswami, Venkatesan
8 Nutov, Zeev
8 Paschos, Vangelis Th.
8 Rothblum, Ron D.
8 Srinivasan, Srikanth
8 Tzameret, Iddo
8 Yehudayoff, Amir
7 Arvind, Vikraman
7 Ben-Sasson, Eli
7 Gur, Tom
7 Korman, Amos
7 Limaye, Nutan
7 Razborov, Aleksandr Aleksandrovich
6 Beyersdorff, Olaf
6 Canetti, Ran
6 Chattopadhyay, Arkadev
6 Dragan, Feodor F.
6 Fomin, Fedor V.
6 Gavoille, Cyril
6 Jansen, Maurice J.
6 Kayal, Neeraj
6 Khot, Subhash Ajit
6 Kindler, Guy
6 Manurangsi, Pasin
6 Saha, Chandan
6 Saxena, Nitin
6 Trevisan, Luca
6 Vidick, Thomas
6 Zuckerman, David
5 Aaronson, Scott
5 Bitansky, Nir
5 Caragiannis, Ioannis
5 Chen, Wenbin
5 Dvir, Zeev
5 Garg, Ankit
5 Gelles, Ran
5 Hrubeš, Pavel
5 Ishai, Yuval
5 Jain, Rahul
5 Kabanets, Valentine
5 Kaklamanis, Christos
5 Kol, Gillat
5 Krajíček, Jan
5 Kushilevitz, Eyal
5 Mustafa, Nabil Hassan
5 Palazuelos, Carlos
5 Pietrzak, Krzysztof
5 Pudlák, Pavel
5 Raghavendra Rao, B. V.
5 Ray, Saurabh
5 Santhanam, Rahul
5 Saptharishi, Ramprasad
5 Ta-Shma, Amnon
5 Viola, Emanuele
4 Alekhnovich, Michael
4 Buss, Samuel R.
4 Chen, Ruiwen
4 Cohen, Gil
4 DasGupta, Bhaskar
4 Escoffier, Bruno
4 Gabizon, Ariel
4 Gawrychowski, Paweł
4 Goldreich, Oded
4 Guo, Siyao
4 Haeupler, Bernhard
4 Harsha, Prahladh
4 Impagliazzo, Russell
4 Junge, Marius
4 Kamath, Pritish
4 Kumar, Mrinal
4 Kutten, Shay
4 Lauria, Massimo
4 Lingas, Andrzej
4 Morizumi, Hiroki
4 Moshkovitz, Dana
4 Neiman, Ofer
4 Ostrovskii, Mikhail Iosifovich
4 Paneth, Omer
4 Rosen, Alon
4 Rothblum, Guy N.
4 Safra, Shmuel
4 Saurabh, Nitin
4 Skorski, Maciej
...and 1,295 more Authors
all top 5

Cited in 138 Serials

108 Theoretical Computer Science
70 SIAM Journal on Computing
62 Computational Complexity
44 Journal of Computer and System Sciences
37 Information Processing Letters
32 Algorithmica
25 Information and Computation
25 Theory of Computing Systems
23 Discrete Applied Mathematics
16 Journal of Combinatorial Optimization
15 Random Structures & Algorithms
13 Combinatorica
13 Distributed Computing
11 Journal of Cryptology
10 SIAM Journal on Discrete Mathematics
9 Artificial Intelligence
9 Annals of Pure and Applied Logic
8 Mathematical Programming. Series A. Series B
7 Discrete & Computational Geometry
7 Theory of Computing
6 Journal of the ACM
5 Discrete Mathematics
5 Operations Research Letters
5 Computational Geometry
5 New Journal of Physics
5 Journal of Discrete Algorithms
4 The Journal of Symbolic Logic
4 Networks
4 Designs, Codes and Cryptography
4 European Journal of Operational Research
4 Bulletin of the American Mathematical Society. New Series
4 Interdisciplinary Information Sciences (IIS)
3 Communications in Mathematical Physics
3 Israel Journal of Mathematics
3 Information Sciences
3 Annals of Operations Research
3 Journal of Global Optimization
3 Cybernetics and Systems Analysis
3 The Bulletin of Symbolic Logic
3 Annals of Mathematics. Second Series
3 Computer Science Review
2 Journal of Philosophical Logic
2 Journal of Pure and Applied Algebra
2 Numerische Mathematik
2 Studia Logica
2 Journal of the American Mathematical Society
2 Discrete Mathematics and Applications
2 Discrete Event Dynamic Systems
2 Proceedings of the National Academy of Sciences of the United States of America
2 Journal of Mathematical Sciences (New York)
2 Annals of Mathematics and Artificial Intelligence
2 Chicago Journal of Theoretical Computer Science
2 RAIRO. Theoretical Informatics and Applications
2 Fundamenta Informaticae
2 Foundations of Computational Mathematics
2 Natural Computing
2 Quantum Information Processing
2 Discrete Optimization
2 Logical Methods in Computer Science
2 Discrete Mathematics, Algorithms and Applications
2 ACM Transactions on Computation Theory
1 ACM Computing Surveys
1 Acta Informatica
1 Communications in Algebra
1 International Journal of Theoretical Physics
1 Journal of Mathematical Physics
1 Journal of Statistical Physics
1 Moscow University Mathematics Bulletin
1 Mathematics of Computation
1 Chaos, Solitons and Fractals
1 Acta Mathematica
1 Advances in Mathematics
1 Computing
1 Publications Mathématiques
1 Journal of Combinatorial Theory. Series A
1 Journal of Combinatorial Theory. Series B
1 Journal of Graph Theory
1 Journal of Optimization Theory and Applications
1 Mathematical Systems Theory
1 Proceedings of the American Mathematical Society
1 Synthese
1 European Journal of Combinatorics
1 Social Choice and Welfare
1 Journal of Symbolic Computation
1 New Generation Computing
1 Computers & Operations Research
1 Mathematical and Computer Modelling
1 SIAM Journal on Matrix Analysis and Applications
1 Science in China. Series A
1 Journal of Parallel and Distributed Computing
1 International Journal of Algebra and Computation
1 Differential Geometry and its Applications
1 MSCS. Mathematical Structures in Computer Science
1 International Journal of Foundations of Computer Science
1 Communications in Statistics. Simulation and Computation
1 Journal de Mathématiques Pures et Appliquées. Neuvième Série
1 Linear Algebra and its Applications
1 SIAM Review
1 Archive for Mathematical Logic
1 Journal of Mathematical Imaging and Vision
...and 38 more Serials

Citations by Year