×

zbMATH — the first resource for mathematics

Computational Complexity

Short Title: Comput. Complexity
Publisher: Springer (Birkhäuser), Basel
ISSN: 1016-3328; 1420-8954/e
Online: http://link.springer.com/journal/volumesAndIssues/37
Comments: Indexed cover-to-cover
Documents Indexed: 496 Publications (since 1991)
References Indexed: 294 Publications with 8,565 References.
all top 5

Latest Issues

30, No. 2 (2021)
30, No. 1 (2021)
29, No. 2 (2020)
29, No. 1 (2020)
28, No. 4 (2019)
28, No. 3 (2019)
28, No. 2 (2019)
28, No. 1 (2019)
27, No. 4 (2018)
27, No. 3 (2018)
27, No. 2 (2018)
27, No. 1 (2018)
26, No. 4 (2017)
26, No. 3 (2017)
26, No. 2 (2017)
26, No. 1 (2017)
25, No. 4 (2016)
25, No. 3 (2016)
25, No. 2 (2016)
25, No. 1 (2016)
24, No. 4 (2015)
24, No. 3 (2015)
24, No. 2 (2015)
24, No. 1 (2015)
23, No. 4 (2014)
23, No. 3 (2014)
23, No. 2 (2014)
23, No. 1 (2014)
22, No. 4 (2013)
22, No. 3 (2013)
22, No. 2 (2013)
22, No. 1 (2013)
21, No. 4 (2012)
21, No. 3 (2012)
21, No. 2 (2012)
21, No. 1 (2012)
20, No. 4 (2011)
20, No. 3 (2011)
20, No. 2 (2011)
20, No. 1 (2011)
19, No. 4 (2010)
19, No. 3 (2010)
19, No. 2 (2010)
19, No. 1 (2010)
18, No. 4 (2009)
18, No. 3 (2009)
18, No. 2 (2009)
18, No. 1 (2009)
17, No. 4 (2008)
17, No. 3 (2008)
17, No. 2 (2008)
17, No. 1 (2008)
16, No. 4 (2007)
16, No. 3 (2007)
16, No. 2 (2007)
16, No. 1 (2007)
15, No. 4 (2006)
15, No. 3 (2006)
15, No. 2 (2006)
15, No. 1 (2006)
14, No. 4 (2005)
14, No. 3 (2005)
14, No. 2 (2005)
14, No. 1 (2005)
13, No. 3-4 (2004)
13, No. 1-2 (2004)
12, No. 3-4 (2003)
12, No. 1-2 (2003)
11, No. 3-4 (2002)
11, No. 1-2 (2002)
10, No. 4 (2001)
10, No. 3 (2001)
10, No. 2 (2001)
10, No. 1 (2001)
9, No. 3-4 (2000)
9, No. 2 (2000)
9, No. 1 (2000)
8, No. 4 (1999)
8, No. 3 (1999)
8, No. 2 (1999)
8, No. 1 (1999)
7, No. 4 (1998)
7, No. 3 (1998)
7, No. 2 (1998)
7, No. 1 (1998)
6, No. 4 (1997)
6, No. 3 (1997)
6, No. 2 (1997)
6, No. 1 (1997)
5, No. 3-4 (1995)
5, No. 2 (1995)
5, No. 1 (1995)
4, No. 4 (1994)
4, No. 3 (1994)
4, No. 2 (1994)
4, No. 1 (1994)
3, No. 4 (1993)
3, No. 3 (1993)
3, No. 2 (1993)
3, No. 1 (1993)
...and 6 more Volumes
all top 5

Authors

13 Impagliazzo, Russell
13 Shpilka, Amir
12 Goldreich, Oded
12 Pitassi, Toniann
11 Fortnow, Lance J.
11 Grigor’ev, Dmitriĭ Yur’evich
11 Shaltiel, Ronen
11 Wigderson, Avi
9 Raz, Ran
8 Allender, Eric W.
8 Kabanets, Valentine
8 Meir, Or
8 Razborov, Aleksandr Aleksandrovich
8 Smolensky, Roman
8 van Melkebeek, Dieter
7 Beigel, Richard
7 Dvir, Zeev
7 Viola, Emanuele
6 Alekhnovich, Michael
6 Håstad, Johan Torkel
6 Karpinski, Marek
6 Nisan, Noam
6 Saxena, Nitin
5 Applebaum, Benny
5 Beame, Paul W.
5 Ben-Sasson, Eli
5 Borodin, Allan B.
5 Dinur, Irit
5 Gál, Anna
5 Kayal, Neeraj
5 Lee, Troy
5 Lovett, Shachar
5 Lund, Carsten
5 Pudlák, Pavel
5 Qiao, Youming
5 Sherstov, Alexander A.
5 Shparlinski, Igor E.
5 Vadhan, Salil P.
5 von zur Gathen, Joachim
5 Williams, Richard Ryan
4 Arvind, Vikraman
4 Babai, László
4 Bshouty, Nader H.
4 Bürgisser, Peter
4 Cai, Jin-Yi
4 Damm, Carsten
4 McKenzie, Pierre
4 Mix Barrington, David A.
4 Pavan, Aduri
4 Saks, Michael E.
4 Sgall, Jiří
4 Sudan, Madhu
4 Thierauf, Thomas
4 Umans, Christopher
4 Vinodchandran, N. Variyam
4 Yehudayoff, Amir
4 Zuckerman, David
3 Alon, Noga M.
3 Basu, Saugata
3 Beimel, Amos
3 Bläser, Markus
3 Bro Miltersen, Peter
3 Buhrman, Harry
3 Cook, Stephen Arthur
3 Feige, Uriel
3 Feigenbaum, Joan
3 Giesbrecht, Mark W.
3 Goldberg, Leslie Ann
3 Gopalan, Parikshit
3 Gur, Tom
3 Gutfreund, Dan
3 Hemaspaandra, Lane A.
3 Hitchcock, John M.
3 Ishai, Yuval
3 Ivanyos, Gábor
3 Koiran, Pascal
3 Krause, Matthias
3 Kushilevitz, Eyal
3 Lu, Pinyan
3 Maciel, Alexis
3 Mahajan, Meena
3 Mukhopadhyay, Partha
3 Newman, Ilan I.
3 Ron, Dana
3 Rudich, Steven
3 Safra, Shmuel
3 Saha, Chandan
3 Schost, Éric
3 Shoup, Victor
3 Srinivasan, Srikanth
3 Ta-Shma, Amnon
3 Tiwari, Prasoon
3 Trevisan, Luca
3 Volk, Ben Lee
3 Vorob’ëv, Nikolaĭ N. jun.
3 Watanabe, Osamu
3 Yukna, Stasys P.
2 Àlvarez, Carme
2 Ambainis, Andris
2 Artemenko, Sergei
...and 514 more Authors

Publications by Year

Citations contained in zbMATH Open

387 Publications have been cited 3,162 times in 2,236 Documents Cited by Year
Derandomizing polynomial identity tests means proving circuit lower bounds. Zbl 1089.68042
Kabanets, Valentine; Impagliazzo, Russell
121
2004
A new recursion-theoretic characterization of the polytime functions. Zbl 0766.68037
Bellantoni, Stephen; Cook, Stephen
96
1992
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
90
1991
The electrical resistance of a graph captures its commute and cover times. Zbl 0905.60049
Chandra, Ashok K.; Raghavan, Prabhakar; Ruzzo, Walter L.; Smolensky, Roman; Tiwari, Prasoon
77
1997
On the degree of Boolean functions as real polynomials. Zbl 0829.68047
Nisan, Noam; Szegedy, Mario
60
1994
Computing Frobenius maps and factoring polynomials. Zbl 0778.11076
von zur Gathen, Joachim; Shoup, Victor
55
1992
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
49
1993
Majority gates vs. general weighted threshold gates. Zbl 0770.68054
Goldmann, Mikael; Håstad, Johan; Razborov, Alexander
43
1992
The hardness of approximation: Gap location. Zbl 0822.68052
Petrank, Erez
42
1994
On lower bounds for read-\(k\)-times branching programs. Zbl 0777.68043
Borodin, A.; Razborov, A.; Smolensky, R.
42
1993
On the hardness of approximating Multicut and Sparsest-Cut. Zbl 1132.68418
Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D.
39
2006
On the power of small-depth threshold circuits. Zbl 0774.68060
Håstad, Johan; Goldmann, Mikael
39
1991
On the complexity of approximating \(k\)-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
37
2006
Exponential lower bounds for the pigeonhole principle. Zbl 0784.03034
Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell
37
1993
Improved low-density subset sum algorithms. Zbl 0768.11049
Coster, Matthijs J.; Joux, Antoine; LaMacchia, Brian A.; Odlyzko, Andrew M.; Schnorr, Claus-Peter; Stern, Jacques
36
1992
Lower bounds on arithmetic circuits via partial derivatives. Zbl 0890.68074
Nisan, Noam; Wigderson, Avi
33
1997
On ACC. Zbl 0835.68040
Beigel, Richard; Tarui, Jun
32
1994
Computationally private randomizing polynomials and their applications. Zbl 1143.94009
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal
28
2006
Derandomized graph products. Zbl 0816.60070
Alon, Noga; Feige, Uriel; Wigderson, Avi; Zuckerman, David
27
1995
On the complexity of computing determinants. Zbl 1061.68185
Kaltofen, Erich; Villard, Gilles
26
2004
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Zbl 1133.68024
Micciancio, Daniele
26
2007
Property testing lower bounds via communication complexity. Zbl 1253.68142
Blais, Eric; Brody, Joshua; Matulef, Kevin
26
2012
Lower bounds and separations for constant depth multilinear circuits. Zbl 1213.68319
Raz, Ran; Yehudayoff, Amir
25
2009
Perceptrons, PP, and the polynomial hierarchy. Zbl 0829.68059
Beigel, Richard
25
1994
Depth-3 arithmetic circuits over fields of characteristic zero. Zbl 0998.68064
Shpilka, Amir; Wigderson, Avi
24
2001
Deterministic polynomial identity testing in non-commutative models. Zbl 1096.68070
Raz, Ran; Shpilka, Amir
23
2005
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
22
1991
Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129
Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří
21
1999
Representing Boolean functions as polynomials modulo composite numbers. Zbl 0829.68057
Barrington, David A. Mix; Beigel, Richard; Rudich, Steven
21
1994
On the efficiency of effective Nullstellensätze. Zbl 0824.68051
Giusti, Marc; Heintz, Joos; Sabia, Juan
21
1993
The complexity of membership problems for circuits over sets of natural numbers. Zbl 1133.68028
McKenzie, Pierre; Wagner, Klaus W.
21
2007
Lower bounds for the polynomial calculus. Zbl 1026.03043
Razborov, Alexander A.
20
1998
On randomized one-round communication complexity. Zbl 0942.68059
Kremer, Ilan; Nisan, Noam; Ron, Dana
20
1999
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting. Zbl 0890.03030
Buss, S.; Impagliazzo, R.; Krajíček, J.; Pudlák, P.; Razborov, A. A.; Sgall, J.
20
1997
Counting connected components of a semialgebraic set in subexponential time. Zbl 0900.68253
Grigor’ev, D. Yu.; Vorobjov, N. N. jun.
20
1992
Cartesian graph factorization at logarithmic cost per edge. Zbl 0770.68064
Aurenhammer, F.; Hagauer, J.; Imrich, W.
20
1992
Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116
Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David
19
2015
Complexity of Positivstellensatz proofs for the knapsack. Zbl 0992.68077
Grigoriev, D.
19
2001
Derandomizing Arthur-Merlin games using hitting sets. Zbl 1085.68058
Miltersen, Peter Bro; Vinodchandran, N. V.
18
2005
Quantum Arthur-Merlin games. Zbl 1085.68052
Watrous, Chris John
18
2005
Super-logarithmic depth lower bounds via the direct sum in communication complexity. Zbl 0851.68034
Karchmer, Mauricio; Raz, Ran; Wigderson, Avi
18
1995
Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
18
2017
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Zbl 0963.68082
Greenhill, Catherine
17
2000
Symmetric alternation captures BPP. Zbl 0912.68054
Russell, Alexander; Sundaram, Ravi
16
1998
Disjointness is hard in the multiparty number-on-the-forehead model. Zbl 1213.68314
Lee, Troy; Shraibman, Adi
16
2009
Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH. Zbl 1205.05240
Briand, Emmanuel; Orellana, Rosa; Rosas, Mercedes
16
2009
Toward a model for backtracking and dynamic programming. Zbl 1252.68130
Alekhnovich, Michael; Borodin, Allan; Buresh-Oppenheim, Joshua; Impagliazzo, Russell; Magen, Avner; Pitassi, Toniann
16
2011
Towards proving strong direct product theorems. Zbl 1084.68542
Shaltiel, Ronen
15
2003
The alternation hierarchy for sublogarithmic space is infinite. Zbl 0796.68099
von Braunmühl, Burchard; Gengler, Romain; Rettinger, Robert
15
1993
Lower bounds for linear locally decodable codes and private information retrieval. Zbl 1113.68049
Goldreich, Oded; Karloff, Howard; Schulman, Leonard J.; Trevisan, Luca
15
2006
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
15
2011
Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022
Krause, Matthias; Pudlák, Pavel
14
1998
The complexity of matrix rank and feasible systems of linear equations. Zbl 0949.68071
Allender, Eric; Beals, Robert; Ogihara, Mitsunori
14
1999
Extractors and rank extractors for polynomial sources. Zbl 1210.68136
Dvir, Zeev; Gabizon, Ariel; Wigderson, Avi
14
2009
On sunflowers and matrix multiplication. Zbl 1268.05223
Alon, Noga; Shpilka, Amir; Umans, Christopher
14
2013
Finding maximal orders in semisimple algebras over \(\mathbb{Q}\). Zbl 0792.16020
Ivanyos, Gábor; Rónyai, Lajos
14
1993
A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. Zbl 1125.68054
Beame, Paul; Pitassi, Toniann; Segerlind, Nathan; Wigderson, Avi
14
2006
\(NC^ 1\): The automata-theoretic viewpoint. Zbl 0774.68048
McKenzie, Pierre; Péladeau, Pierre; Thérien, Denis
14
1991
A complexity gap for tree resolution. Zbl 0994.03005
Riis, Søren
13
2002
Non-automatizability of bounded-depth Frege proofs. Zbl 1058.03063
Bonet, Maria Luisa; Domingo, Carlos; Gavaldà, Ricard; Maciel, Alexis; Pitassi, Toniann
13
2004
Approximation resistant predicates from pairwise independence. Zbl 1214.68172
Austrin, Per; Mossel, Elchanan
13
2009
A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Zbl 1286.68208
Seto, Kazuhisa; Tamaki, Suguru
13
2013
On interactive proofs with a laconic prover. Zbl 1053.68045
Goldreich, Oded; Vadhan, Salil; Wigderson, Avi
13
2002
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Zbl 1082.14065
Grigoriev, Dima; Pasechnik, Dmitrii V.
13
2005
Balancing syntactically multilinear arithmetic circuits. Zbl 1188.68367
Raz, Ran; Yehudayoff, Amir
13
2008
Pseudorandomness and average-case complexity via uniform reductions. Zbl 1133.68023
Trevisan, Luca; Vadhan, Salil
13
2007
Perfect parallel repetition theorem for quantum XOR proof systems. Zbl 1145.81017
Cleve, Richard; Slofstra, William; Unger, Falk; Upadhyay, Sarvagya
13
2008
Graph isomorphism is low for PP. Zbl 0770.68055
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
13
1992
On the complexity of simulating space-bounded quantum computations. Zbl 1068.68066
Watrous, John
12
2003
The complexity of constructing pseudorandom generators from hard functions. Zbl 1061.68077
Viola, Emanuele
12
2004
Randomness in interactive proofs. Zbl 0802.68053
Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi
12
1993
Polynomial identity testing for depth 3 circuits. Zbl 1173.94470
Kayal, Neeraj; Saxena, Nitin
12
2007
Decompositions of algebras over \(\mathbb{R}\) and \(\mathbb{C}\). Zbl 0774.68069
Eberly, Wayne
12
1991
Existence and efficient construction of fast Fourier transforms on supersolvable groups. Zbl 0778.65092
Baum, Ulrich
12
1991
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
12
2013
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
11
1995
The sum of \(D\) small-bias generators fools polynomials of degree \(D\). Zbl 1217.68157
Viola, Emanuele
11
2009
When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one. Zbl 0829.68058
Beigel, Richard
11
1994
Optimality of size-width tradeoffs for resolution. Zbl 1024.03012
Bonet, Maria Luisa; Galesi, Nicola
11
2001
Halfspace matrices. Zbl 1147.68027
Sherstov, Alexander A.
11
2008
Limits on the hardness of lattice problems in \(\ell_{p}\) norms. Zbl 1149.68039
Peikert, Chris
11
2008
Pseudorandomness for approximate counting and sampling. Zbl 1125.68058
Shaltiel, Ronen; Umans, Christopher
11
2006
Efficient and optimal exponentiation in finite fields. Zbl 0788.68074
von zur Gathen, Joachim
11
1991
Decomposition of algebras over finite fields and number fields. Zbl 0774.68068
Eberly, Wayne
11
1991
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
10
2005
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs. Zbl 0962.68075
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
10
1999
Communication complexity towards lower bounds on circuit depth. Zbl 1053.68048
Edmonds, Jeff; Impagliazzo, Russell; Rudich, Steven; Sgall, Jiří
10
2001
Lower bounds for monotone span programs. Zbl 0870.68072
Beimel, Amos; Gál, Anna; Paterson, Mike
10
1997
On the complexity of computing Kronecker coefficients. Zbl 1367.05012
Pak, Igor; Panova, Greta
10
2017
Random CNF’s are hard for the polynomial calculus. Zbl 1216.03064
Ben-Sasson, Eli; Impagliazzo, Russell
10
2010
A dichotomy for real weighted Holant problems. Zbl 1336.68099
Huang, Sangxia; Lu, Pinyan
10
2016
A characterization of span program size and improved lower bounds for monotone span programs. Zbl 1039.68051
Gàl, Anna
10
2001
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
10
2018
Parameterized complexity of constraint satisfaction problems. Zbl 1085.68068
Marx, Dániel
9
2005
Complexity theoretic hardness results for query learning. Zbl 0903.68157
Aizenstein, Howard; Hegedűs, Tibor; Hellerstein, Lisa; Pitt, Leonard
9
1998
Counting curves and their projections. Zbl 0990.68642
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
9
1997
On the complexity of vertex-disjoint length-restricted path problems. Zbl 1085.68066
Bley, Andreas
9
2003
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
Lipschitz continuous ordinary differential equations are polynomial-space complete. Zbl 1232.03031
Kawamura, Akitoshi
9
2010
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
Grigoriev, Dima; Podolskii, Vladimir V.
9
2015
Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\). Zbl 1425.68127
Göös, Mika; Kamath, Pritish; Pitassi, Toniann; Watson, Thomas
3
2019
Tensor surgery and tensor rank. Zbl 1414.05206
Christandl, Matthias; Zuiddam, Jeroen
2
2019
Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Zbl 1415.65098
Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen
2
2019
Simulation theorems via pseudo-random properties. Zbl 07145985
Chattopadhyay, Arkadev; Koucký, Michal; Loff, Bruno; Mukhopadhyay, Sagnik
2
2019
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
10
2018
Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
9
2018
The landscape of communication complexity classes. Zbl 1398.68180
Göös, Mika; Pitassi, Toniann; Watson, Thomas
5
2018
Non-interactive proofs of proximity. Zbl 1391.68098
Gur, Tom; Rothblum, Ron D.
3
2018
The average sensitivity of bounded-depth formulas. Zbl 1396.68050
Rossman, Benjamin
2
2018
An adaptivity hierarchy theorem for property testing. Zbl 1403.68331
Canonne, Clément L.; Gur, Tom
2
2018
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity. Zbl 1402.68073
Dinur, Irit; Meir, Or
1
2018
On space and depth in resolution. Zbl 06974168
Razborov, Alexander
1
2018
Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
18
2017
On the complexity of computing Kronecker coefficients. Zbl 1367.05012
Pak, Igor; Panova, Greta
10
2017
On vanishing of Kronecker coefficients. Zbl 1382.68093
Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael
9
2017
Information-theoretic approximations of the nonnegative rank. Zbl 1381.94044
Braun, Gábor; Jain, Rahul; Lee, Troy; Pokutta, Sebastian
6
2017
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Zbl 1378.68049
Doron, Dean; Sarid, Amir; Ta-Shma, Amnon
4
2017
The minimum oracle circuit size problem. Zbl 1408.68065
Allender, Eric; Holden, Dhiraj; Kabanets, Valentine
4
2017
Graph isomorphism, color refinement, and compactness. Zbl 1379.05080
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
4
2017
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games. Zbl 1371.68094
Aydınlıoğlu, Barış; van Melkebeek, Dieter
3
2017
On the structure of Boolean functions with small spectral norm. Zbl 1371.94704
Shpilka, Amir; Tal, Avishay; Volk, Ben lee
3
2017
Fourier concentration from shrinkage. Zbl 1371.68092
Impagliazzo, Russell; Kabanets, Valentine
3
2017
List-decoding Barnes-Wall lattices. Zbl 1405.94133
Grigorescu, Elena; Peikert, Chris
2
2017
Sunflowers and testing triangle-freeness of functions. Zbl 1379.68340
Haviv, Ishay; Xie, Ning
2
2017
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
2
2017
Sparse affine-invariant linear codes are locally testable. Zbl 1381.94114
Ben-Sasson, Eli; Ron-Zewi, Noga; Sudan, Madhu
1
2017
Multipartite quantum correlation and communication complexities. Zbl 1371.68089
Jain, Rahul; Wei, Zhaohui; Yao, Penghui; Zhang, Shengyu
1
2017
Block-symmetric polynomials correlate with parity better than symmetric. Zbl 1379.68153
Green, Frederic; Kreymer, Daniel; Viola, Emanuele
1
2017
On the connection between interval size functions and path counting. Zbl 1401.68107
Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris
1
2017
Low-degree test with polynomially small error. Zbl 1378.68052
Moshkovitz, Dana
1
2017
Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Zbl 1382.68110
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin; Thierauf, Thomas
1
2017
A dichotomy for real weighted Holant problems. Zbl 1336.68099
Huang, Sangxia; Lu, Pinyan
10
2016
Cryptographic hardness of random local functions. Survey. Zbl 1360.94293
Applebaum, Benny
3
2016
Combinatorial PCPs with short proofs. Zbl 1336.68090
Meir, Or
2
2016
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Zbl 1345.68126
Applebaum, Benny; Artemenko, Sergei; Shaltiel, Ronen; Yang, Guang
2
2016
Lower bounds for depth-three arithmetic circuits with small bottom fanin. Zbl 1345.68161
Kayal, Neeraj; Saha, Chandan
2
2016
Collapse of the hierarchy of constant-depth exact quantum circuits. Zbl 1353.68097
Takahashi, Yasuhiro; Tani, Seiichiro
2
2016
The complexity of estimating min-entropy. Zbl 1336.68109
Watson, Thomas
1
2016
Relativizing small complexity classes and their theories. Zbl 1336.68084
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
1
2016
Kolmogorov width of discrete linear spaces: an approach to matrix rigidity. Zbl 1344.68100
Samorodnitsky, Alex; Shkredov, Ilya; Yekhanin, Sergey
1
2016
Factors of low individual degree polynomials. Zbl 1345.68292
Oliveira, Rafael
1
2016
Quantum query complexity of almost all functions with fixed on-set size. Zbl 1353.68094
Ambainis, Andris; Iwama, Kazuo; Nakanishi, Masaki; Nishimura, Harumichi; Raymond, Rudy; Tani, Seiichiro; Yamashita, Shigeru
1
2016
Testing list \(H\)-homomorphisms. Zbl 1353.68139
Yoshida, Yuichi
1
2016
Affine extractors over large fields with exponential error. Zbl 1419.11132
Bourgain, Jean; Dvir, Zeev; Leeman, Ethan
1
2016
Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116
Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David
19
2015
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
Grigoriev, Dima; Podolskii, Vladimir V.
9
2015
Deterministic polynomial identity tests for multilinear bounded-read formulae. Zbl 1346.68105
Anderson, Matthew; van Melkebeek, Dieter; Volkovich, Ilya
6
2015
A parallel repetition theorem for entangled projection games. Zbl 1329.68116
Dinur, Irit; Steurer, David; Vidick, Thomas
6
2015
Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035
Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir
6
2015
Unifying known lower bounds via geometric complexity theory. Zbl 1329.68123
Grochow, Joshua A.
6
2015
Quantum algorithms for learning symmetric juntas via the adversary bound. Zbl 1329.68115
Belovs, Aleksandrs
5
2015
Read-once polynomial identity testing. Zbl 1329.68147
Shpilka, Amir; Volkovich, Ilya
5
2015
Lower bounds for testing triangle-freeness in Boolean functions. Zbl 1332.68056
Bhattacharyya, Arnab; Xie, Ning
4
2015
On the complexity of inverting integer and polynomial matrices. Zbl 1333.68302
Storjohann, Arne
3
2015
Composition of semi-LTCs by two-wise tensor products. Zbl 1336.94084
Ben-Sasson, Eli; Viderman, Michael
3
2015
The NOF multiparty communication complexity of composed functions. Zbl 1329.68103
Ada, Anil; Chattopadhyay, Arkadev; Fawzi, Omar; Nguyen, Phuong
3
2015
On rigid matrices and \(U\)-polynomials. Zbl 1333.68120
Alon, Noga; Cohen, Gil
1
2015
The remote set problem on lattices. Zbl 1332.68077
Haviv, Ishay
1
2015
Rank-one quantum games. Zbl 1328.81063
Cooney, T.; Junge, M.; Palazuelos, C.; Pérez-García, D.
1
2015
Limits on alternation trading proofs for time-space lower bounds. Zbl 1338.68080
Buss, Samuel R.; Williams, Ryan
1
2015
On the power of non-adaptive learning graphs. Zbl 1314.68134
Belovs, Aleksandrs; Rosmanis, Ansis
6
2014
Randomness buys depth for approximate counting. Zbl 1318.68091
Viola, Emanuele
4
2014
On uniformity and circuit lower bounds. Zbl 1314.68139
Santhanam, Rahul; Williams, Ryan
4
2014
Random arithmetic formulas can be reconstructed efficiently. Zbl 1314.68390
Gupta, Ankit; Kayal, Neeraj; Qiao, Youming
4
2014
Short lists for shortest descriptions in short time. Zbl 1366.68103
Teutsch, Jason
4
2014
The correct exponent for the Gotsman-Linial conjecture. Zbl 1314.68138
Kane, Daniel M.
3
2014
Using elimination theory to construct rigid matrices. Zbl 1366.68076
Kumar, Abhinav; Lokam, Satyanarayana V.; Patankar, Vijay M.; Sarma, M. N. Jayalal
3
2014
Choosing, agreeing, and eliminating in communication complexity. Zbl 1366.68050
Beimel, Amos; Ben Daniel, Sebastian; Kushilevitz, Eyal; Weinreb, Enav
2
2014
Variety evasive sets. Zbl 1308.68166
Dvir, Zeev; Kollár, János; Lovett, Shachar
2
2014
An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic. Zbl 06374277
Mundhenk, Martin; Wei, Felix
2
2014
Combinatorial PCPs with efficient verifiers. Zbl 1318.68087
Meir, Or
1
2014
How low can approximate degree and quantum query complexity be for total Boolean functions? Zbl 1314.68133
Ambainis, Andris; De Wolf, Ronald
1
2014
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. Zbl 1366.68070
Artemenko, Sergei; Shaltiel, Ronen
1
2014
On sunflowers and matrix multiplication. Zbl 1268.05223
Alon, Noga; Shpilka, Amir; Umans, Christopher
14
2013
A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Zbl 1286.68208
Seto, Kazuhisa; Tamaki, Suguru
13
2013
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
12
2013
2-transitivity is insufficient for local testability. Zbl 1283.94130
Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu
9
2013
DNF sparsification and a faster deterministic counting algorithm. Zbl 1286.68230
Gopalan, Parikshit; Meka, Raghu; Reingold, Omer
8
2013
Modular composition modulo triangular sets and applications. Zbl 1311.68199
Poteaux, Adrien; Schost, Éric
6
2013
Query-efficient locally decodable codes of subexponential length. Zbl 1311.94123
Chee, Yeow Meng; Feng, Tao; Ling, San; Wang, Huaxiong; Zhang, Liang Feng
5
2013
Is Valiant-Vazirani’s isolation probability improvable? Zbl 1286.68167
Dell, Holger; Kabanets, Valentine; van Melkebeek, Dieter; Watanabe, Osamu
4
2013
Resource trade-offs in syntactically multilinear arithmetic circuits. Zbl 1286.68135
Jansen, Maurice; Mahajan, Meena; Raghavendra Rao, B. V.
3
2013
Improved approximation of linear threshold functions. Zbl 1273.68292
Diakonikolas, Ilias; Servedio, Rocco A.
3
2013
Small space analogues of Valiant’s classes and the limitations of skew formulas. Zbl 1279.68083
Mahajan, Meena; Raghavendra Rao, B. V.
3
2013
A strong direct product theorem for quantum query complexity. Zbl 1286.68156
Lee, Troy; Roland, Jérémie
2
2013
Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields. Zbl 1290.68049
Lovett, Shachar; Mukhopadhyay, Partha; Shpilka, Amir
2
2013
A case of depth-3 identity testing, sparse factorization and duality. Zbl 1311.68201
Saha, Chandan; Saptharishi, Ramprasad; Saxena, Nitin
2
2013
Derandomized parallel repetition theorems for free games. Zbl 1290.68043
Shaltiel, Ronen
1
2013
Pseudorandom generators for combinatorial checkerboards. Zbl 1290.68042
Watson, Thomas
1
2013
Comparing the strength of query types in property testing: the case of \(k\)-colorability. Zbl 1280.68091
Ben-Eliezer, Ido; Kaufman, Tali; Krivelevich, Michael; Ron, Dana
1
2013
Property testing lower bounds via communication complexity. Zbl 1253.68142
Blais, Eric; Brody, Joshua; Matulef, Kevin
26
2012
Extractors for varieties. Zbl 1280.68293
Dvir, Zeev
8
2012
On the security of Goldreich’s one-way function. Zbl 1280.68092
Bogdanov, Andrej; Qiao, Youming
6
2012
Holographic reduction, interpolation and hardness. Zbl 1282.68120
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
6
2012
Improved direct product theorems for randomized query complexity. Zbl 1253.68147
Drucker, Andrew
5
2012
Pseudorandom generators, typically-correct derandomization, and circuit lower bounds. Zbl 1242.68108
Kinne, Jeff; van Melkebeek, Dieter; Shaltiel, Ronen
4
2012
Bounded-depth circuits cannot sample good codes. Zbl 1282.68125
Lovett, Shachar; Viola, Emanuele
4
2012
A quantum characterization of NP. Zbl 1288.68079
Blier, Hugue; Tapp, Alain
3
2012
Inapproximability of the Tutte polynomial of a planar graph. Zbl 1282.68122
Goldberg, Leslie Ann; Jerrum, Mark
3
2012
Random low-degree polynomials are hard to approximate. Zbl 1280.68090
Ben-Eliezer, Ido; Hod, Rani; Lovett, Shachar
2
2012
...and 287 more Documents
all top 5

Cited by 2,633 Authors

24 Goldreich, Oded
21 Allender, Eric W.
21 Cai, Jin-Yi
21 Fortnow, Lance J.
19 Servedio, Rocco A.
19 Wigderson, Avi
18 Arvind, Vikraman
18 Grigor’ev, Dmitriĭ Yur’evich
18 Pitassi, Toniann
16 Applebaum, Benny
15 Mahajan, Meena
15 Yukna, Stasys P.
14 Meir, Or
14 Schost, Éric
14 Sudan, Madhu
13 Basu, Saugata
13 Buhrman, Harry
13 Impagliazzo, Russell
13 Ivanyos, Gábor
12 Beyersdorff, Olaf
12 Glaßer, Christian
12 Hemaspaandra, Lane A.
12 Ishai, Yuval
12 Sherstov, Alexander A.
12 Shparlinski, Igor E.
12 Viola, Emanuele
11 Ben-Sasson, Eli
11 Bürgisser, Peter
11 Feige, Uriel
11 Kabanets, Valentine
11 Karpinski, Marek
11 Okhotin, Alexander
11 Shpilka, Amir
11 Williams, Richard Ryan
10 Chattopadhyay, Arkadev
10 Chiesa, Alessandro
10 Dvir, Zeev
10 Gál, Anna
10 Guruswami, Venkatesan
10 Köbler, Johannes
10 Krajíček, Jan
10 Lauria, Massimo
10 Pudlák, Pavel
10 Qiao, Youming
10 Raghavendra Rao, B. V.
10 Santhanam, Rahul
10 Saxena, Nitin
10 Shaltiel, Ronen
10 Thérien, Denis
10 van Melkebeek, Dieter
10 Vinodchandran, N. Variyam
10 von zur Gathen, Joachim
9 Atserias, Albert
9 Beigel, Richard
9 Braverman, Mark
9 Filmus, Yuval
9 Göös, Mika
9 Kayal, Neeraj
9 Koiran, Pascal
9 Limaye, Nutan
9 McKenzie, Pierre
9 O’Donnell, Ryan
9 Podol’skiĭ, Vladimir Vladimirovich
9 Raz, Ran
9 Srinivasan, Srikanth
8 Beimel, Amos
8 Bollig, Beate
8 Buss, Samuel R.
8 Dal Lago, Ugo
8 de Wolf, Ronald Michiel
8 Dinur, Irit
8 Grigorescu, Elena
8 Gur, Tom
8 Håstad, Johan Torkel
8 Itsykson, Dmitry M.
8 Jansen, Maurice J.
8 Jeż, Artur
8 Khot, Subhash Ajit
8 Lovett, Shachar
8 Martin, Barnaby D.
8 Müller, Moritz
8 Pavan, Aduri
8 Rónyai, Lajos
8 Rothblum, Ron D.
8 Vollmer, Heribert
8 Watanabe, Osamu
7 Ambainis, Andris
7 Babai, László
7 Beame, Paul W.
7 Belovs, Aleksandrs
7 Bogdanov, Andrej
7 Cucker, Felipe
7 Galesi, Nicola
7 Geffert, Viliam
7 Ikenmeyer, Christian
7 Koucký, Michal
7 Kurpisz, Adam
7 Lipton, Richard J.
7 Mossel, Elchanan
7 Panova, Greta
...and 2,533 more Authors
all top 5

Cited in 240 Journals

230 Theoretical Computer Science
173 Computational Complexity
124 Journal of Computer and System Sciences
94 SIAM Journal on Computing
84 Information and Computation
77 Information Processing Letters
69 Theory of Computing Systems
62 Algorithmica
43 Journal of Symbolic Computation
36 Discrete Applied Mathematics
27 Mathematics of Computation
27 Journal of Cryptology
26 Annals of Pure and Applied Logic
24 Discrete Mathematics
24 Journal of Complexity
20 Journal of Algebra
19 Designs, Codes and Cryptography
17 Random Structures & Algorithms
17 International Journal of Foundations of Computer Science
16 Mathematical Programming. Series A. Series B
15 Discrete & Computational Geometry
15 Journal of Combinatorial Optimization
14 Combinatorica
14 Foundations of Computational Mathematics
13 SIAM Journal on Discrete Mathematics
13 Linear Algebra and its Applications
12 Journal of Pure and Applied Algebra
12 The Journal of Symbolic Logic
12 Combinatorics, Probability and Computing
11 Archive for Mathematical Logic
11 Theory of Computing
11 ACM Transactions on Computation Theory
10 Applicable Algebra in Engineering, Communication and Computing
10 The Electronic Journal of Combinatorics
9 Journal of the ACM
8 Communications in Mathematical Physics
8 Journal of Mathematical Sciences (New York)
8 The Bulletin of Symbolic Logic
8 Quantum Information Processing
8 Logical Methods in Computer Science
7 Artificial Intelligence
7 Israel Journal of Mathematics
7 Advances in Mathematics
7 Applied Mathematics and Computation
7 Transactions of the American Mathematical Society
6 International Journal of Algebra and Computation
6 MSCS. Mathematical Structures in Computer Science
6 SIAM Journal on Optimization
6 RAIRO. Theoretical Informatics and Applications
6 Discrete Optimization
5 Journal of Mathematical Physics
5 The Annals of Probability
5 Journal of the American Mathematical Society
5 Neural Computation
5 Bulletin of the American Mathematical Society. New Series
5 Finite Fields and their Applications
5 Annals of Mathematics. Second Series
5 Journal of the European Mathematical Society (JEMS)
5 Lobachevskii Journal of Mathematics
5 SIAM Journal on Applied Algebra and Geometry
4 Computers & Mathematics with Applications
4 Computing
4 Journal of Combinatorial Theory. Series A
4 Journal of Number Theory
4 Mathematics of Operations Research
4 Advances in Applied Mathematics
4 Operations Research Letters
4 Probability Theory and Related Fields
4 European Journal of Operational Research
4 Journal of Algebraic Combinatorics
4 The Journal of Fourier Analysis and Applications
4 Chicago Journal of Theoretical Computer Science
4 LMS Journal of Computation and Mathematics
4 Comptes Rendus. Mathématique. Académie des Sciences, Paris
4 ACM Transactions on Computational Logic
4 International Journal of Number Theory
4 Algorithms
3 Information Sciences
3 Mathematics and Computers in Simulation
3 Mathematical Systems Theory
3 Proceedings of the American Mathematical Society
3 European Journal of Combinatorics
3 Applied Mathematics Letters
3 Machine Learning
3 Japan Journal of Industrial and Applied Mathematics
3 Computational Geometry
3 RAIRO. Informatique Théorique et Applications
3 Constraints
3 Natural Computing
3 Journal of Mathematical Cryptology
3 Advances in Mathematics of Communications
3 Forum of Mathematics, Sigma
3 Prikladnaya Diskretnaya Matematika
2 Acta Informatica
2 Communications in Algebra
2 Journal of Statistical Physics
2 Linear and Multilinear Algebra
2 Mathematical Notes
2 Nuclear Physics. B
2 Arkiv för Matematik
...and 140 more Journals
all top 5

Cited in 53 Fields

1,625 Computer science (68-XX)
355 Information and communication theory, circuits (94-XX)
298 Combinatorics (05-XX)
242 Mathematical logic and foundations (03-XX)
174 Operations research, mathematical programming (90-XX)
166 Number theory (11-XX)
102 Quantum theory (81-XX)
93 Algebraic geometry (14-XX)
73 Linear and multilinear algebra; matrix theory (15-XX)
71 Probability theory and stochastic processes (60-XX)
64 Group theory and generalizations (20-XX)
63 Commutative algebra (13-XX)
61 Numerical analysis (65-XX)
55 Order, lattices, ordered algebraic structures (06-XX)
52 Field theory and polynomials (12-XX)
51 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
38 Associative rings and algebras (16-XX)
24 Convex and discrete geometry (52-XX)
21 Statistics (62-XX)
17 Statistical mechanics, structure of matter (82-XX)
14 Functional analysis (46-XX)
11 Nonassociative rings and algebras (17-XX)
11 Biology and other natural sciences (92-XX)
8 Dynamical systems and ergodic theory (37-XX)
8 Abstract harmonic analysis (43-XX)
8 Differential geometry (53-XX)
7 Real functions (26-XX)
7 Measure and integration (28-XX)
7 Ordinary differential equations (34-XX)
6 General and overarching topics; collections (00-XX)
6 Category theory; homological algebra (18-XX)
6 Approximations and expansions (41-XX)
6 Operator theory (47-XX)
6 Systems theory; control (93-XX)
5 General algebraic systems (08-XX)
5 Geometry (51-XX)
4 History and biography (01-XX)
4 Manifolds and cell complexes (57-XX)
3 Topological groups, Lie groups (22-XX)
3 Functions of a complex variable (30-XX)
3 Potential theory (31-XX)
3 Partial differential equations (35-XX)
3 Harmonic analysis on Euclidean spaces (42-XX)
3 Algebraic topology (55-XX)
2 \(K\)-theory (19-XX)
2 Difference and functional equations (39-XX)
2 Calculus of variations and optimal control; optimization (49-XX)
2 General topology (54-XX)
1 Several complex variables and analytic spaces (32-XX)
1 Special functions (33-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of particles and systems (70-XX)
1 Relativity and gravitational theory (83-XX)

Citations by Year