×

Computational Complexity

Short Title: Comput. Complexity
Publisher: Springer (Birkhäuser), Basel
ISSN: 1016-3328; 1420-8954/e
Online: https://link.springer.com/journal/37/volumes-and-issues
Comments: Journal; Indexed cover-to-cover
Documents Indexed: 524 Publications (since 1991)
References Indexed: 321 Publications with 9,552 References.
all top 5

Latest Issues

32, No. 2 (2023)
32, No. 1 (2023)
31, No. 2 (2022)
31, No. 1 (2022)
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)
...and 10 more Volumes
all top 5

Authors

14 Impagliazzo, Russell
13 Goldreich, Oded
13 Shpilka, Amir
12 Pitassi, Toniann
12 Shaltiel, Ronen
11 Fortnow, Lance J.
11 Grigor’ev, Dmitriĭ Yur’evich
11 Wigderson, Avi
10 Raz, Ran
9 Kabanets, Valentine
8 Allender, Eric W.
8 Meir, Or
8 Razborov, Aleksandr Aleksandrovich
8 Smolensky, Roman
8 van Melkebeek, Dieter
7 Beigel, Richard
7 Dvir, Zeev
7 Saxena, Nitin
7 Viola, Emanuele
6 Alekhnovich, Michael
6 Håstad, Johan Torkel
6 Karpinski, Marek
6 Nisan, Noam
6 Shparlinski, Igor E.
5 Applebaum, Benny
5 Beame, Paul W.
5 Ben-Sasson, Eli
5 Borodin, Allan B.
5 Cai, Jin-Yi
5 Dinur, Irit
5 Gál, Anna
5 Kayal, Neeraj
5 Kumar, Mrinal
5 Lee, Troy
5 Lovett, Shachar
5 Lund, Carsten
5 Pudlák, Pavel
5 Qiao, Youming
5 Sherstov, Alexander A.
5 Thierauf, Thomas
5 Vadhan, Salil P.
5 Volk, Ben Lee
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 Damm, Carsten
4 Goldberg, Leslie Ann
4 Koiran, Pascal
4 McKenzie, Pierre
4 Mix Barrington, David A.
4 Pavan, Aduri
4 Saks, Michael E.
4 Sgall, Jiří
4 Srinivasan, Srikanth
4 Sudan, Madhu
4 Ta-Shma, Amnon
4 Umans, Christopher
4 Vinodchandran, N. Variyam
4 Yehudayoff, Amir
4 Zuckerman, David
3 Alon, Noga
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 Gopalan, Parikshit
3 Gur, Tom
3 Gutfreund, Dan
3 Haviv, Ishay
3 Hemaspaandra, Lane A.
3 Hitchcock, John M.
3 Ishai, Yuval
3 Ivanyos, Gábor
3 Krause, Matthias
3 Kushilevitz, Eyal
3 Limaye, Nutan
3 Lu, Pinyan
3 Maciel, Alexis
3 Mahajan, Meena
3 Mukhopadhyay, Partha
3 Newman, Ilan I.
3 Paterson, Mike S.
3 Ron, Dana
3 Rudich, Steven
3 Safra, Muli
3 Saha, Chandan
3 Schost, Éric
3 Shoup, Victor
3 Tal, Avishay
3 Tell, Roei
3 Tiwari, Prasoon
3 Trevisan, Luca
...and 561 more Authors

Publications by Year

Citations contained in zbMATH Open

430 Publications have been cited 4,269 times in 2,931 Documents Cited by Year
Derandomizing polynomial identity tests means proving circuit lower bounds. Zbl 1089.68042
Kabanets, Valentine; Impagliazzo, Russell
152
2004
A new recursion-theoretic characterization of the polytime functions. Zbl 0766.68037
Bellantoni, Stephen; Cook, Stephen
122
1992
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
111
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
109
1997
On the degree of Boolean functions as real polynomials. Zbl 0829.68047
Nisan, Noam; Szegedy, Mario
83
1994
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
60
1993
Computing Frobenius maps and factoring polynomials. Zbl 0778.11076
von zur Gathen, Joachim; Shoup, Victor
55
1992
Majority gates vs. general weighted threshold gates. Zbl 0770.68054
Goldmann, Mikael; Håstad, Johan; Razborov, Alexander
52
1992
The hardness of approximation: Gap location. Zbl 0822.68052
Petrank, Erez
52
1994
On the power of small-depth threshold circuits. Zbl 0774.68060
Håstad, Johan; Goldmann, Mikael
50
1991
Lower bounds on arithmetic circuits via partial derivatives. Zbl 0890.68074
Nisan, Noam; Wigderson, Avi
50
1997
On lower bounds for read-\(k\)-times branching programs. Zbl 0777.68043
Borodin, A.; Razborov, A.; Smolensky, R.
49
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
48
1992
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Zbl 1133.68024
Micciancio, Daniele
48
2007
Exponential lower bounds for the pigeonhole principle. Zbl 0784.03034
Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell
47
1993
On the complexity of approximating \(k\)-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
45
2006
On the hardness of approximating Multicut and Sparsest-Cut. Zbl 1132.68418
Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D.
45
2006
Computationally private randomizing polynomials and their applications. Zbl 1143.94009
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal
44
2006
Lower bounds and separations for constant depth multilinear circuits. Zbl 1213.68319
Raz, Ran; Yehudayoff, Amir
37
2009
Deterministic polynomial identity testing in non-commutative models. Zbl 1096.68070
Raz, Ran; Shpilka, Amir
36
2005
On ACC. Zbl 0835.68040
Beigel, Richard; Tarui, Jun
36
1994
Property testing lower bounds via communication complexity. Zbl 1253.68142
Blais, Eric; Brody, Joshua; Matulef, Kevin
34
2012
Depth-3 arithmetic circuits over fields of characteristic zero. Zbl 0998.68064
Shpilka, Amir; Wigderson, Avi
33
2001
On the complexity of computing determinants. Zbl 1061.68185
Kaltofen, Erich; Villard, Gilles
32
2004
On randomized one-round communication complexity. Zbl 0942.68059
Kremer, Ilan; Nisan, Noam; Ron, Dana
32
1999
Quantum Arthur-Merlin games. Zbl 1085.68052
Watrous, Chris John
31
2005
Derandomized graph products. Zbl 0816.60070
Alon, Noga; Feige, Uriel; Wigderson, Avi; Zuckerman, David
31
1995
Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
30
2017
Perceptrons, PP, and the polynomial hierarchy. Zbl 0829.68059
Beigel, Richard
29
1994
Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116
Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David
27
2015
Complexity of Positivstellensatz proofs for the knapsack. Zbl 0992.68077
Grigoriev, D.
27
2001
Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129
Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří
27
1999
Representing Boolean functions as polynomials modulo composite numbers. Zbl 0829.68057
Barrington, David A. Mix; Beigel, Richard; Rudich, Steven
27
1994
Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
26
2018
Derandomizing Arthur-Merlin games using hitting sets. Zbl 1085.68058
Miltersen, Peter Bro; Vinodchandran, N. V.
25
2005
Super-logarithmic depth lower bounds via the direct sum in communication complexity. Zbl 0851.68034
Karchmer, Mauricio; Raz, Ran; Wigderson, Avi
24
1995
On the efficiency of effective Nullstellensätze. Zbl 0824.68051
Giusti, Marc; Heintz, Joos; Sabia, Juan
24
1993
Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH. Zbl 1205.05240
Briand, Emmanuel; Orellana, Rosa; Rosas, Mercedes
24
2009
The complexity of membership problems for circuits over sets of natural numbers. Zbl 1133.68028
McKenzie, Pierre; Wagner, Klaus W.
23
2007
Pseudorandomness and average-case complexity via uniform reductions. Zbl 1133.68023
Trevisan, Luca; Vadhan, Salil
23
2007
Lower bounds for the polynomial calculus. Zbl 1026.03043
Razborov, Alexander A.
23
1998
Balancing syntactically multilinear arithmetic circuits. Zbl 1188.68367
Raz, Ran; Yehudayoff, Amir
23
2008
On interactive proofs with a laconic prover. Zbl 1053.68045
Goldreich, Oded; Vadhan, Salil; Wigderson, Avi
22
2002
Counting connected components of a semialgebraic set in subexponential time. Zbl 0900.68253
Grigor’ev, D. Yu.; Vorobjov, N. N. jun.
22
1992
Cartesian graph factorization at logarithmic cost per edge. Zbl 0770.68064
Aurenhammer, F.; Hagauer, J.; Imrich, W.
22
1992
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
22
1991
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
22
2011
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.
21
1997
On sunflowers and matrix multiplication. Zbl 1268.05223
Alon, Noga; Shpilka, Amir; Umans, Christopher
21
2013
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Zbl 0963.68082
Greenhill, Catherine
21
2000
Finding maximal orders in semisimple algebras over \(\mathbb{Q}\). Zbl 0792.16020
Ivanyos, Gábor; Rónyai, Lajos
20
1993
Extractors and rank extractors for polynomial sources. Zbl 1210.68136
Dvir, Zeev; Gabizon, Ariel; Wigderson, Avi
20
2009
Polynomial identity testing for depth 3 circuits. Zbl 1173.94470
Kayal, Neeraj; Saxena, Nitin
19
2007
A dichotomy for real weighted Holant problems. Zbl 1336.68099
Huang, Sangxia; Lu, Pinyan
19
2016
Lipschitz continuous ordinary differential equations are polynomial-space complete. Zbl 1232.03031
Kawamura, Akitoshi
19
2010
\(NC^ 1\): The automata-theoretic viewpoint. Zbl 0774.68048
McKenzie, Pierre; Péladeau, Pierre; Thérien, Denis
18
1991
Towards proving strong direct product theorems. Zbl 1084.68542
Shaltiel, Ronen
18
2003
Perfect parallel repetition theorem for quantum XOR proof systems. Zbl 1145.81017
Cleve, Richard; Slofstra, William; Unger, Falk; Upadhyay, Sarvagya
18
2008
Limits on the hardness of lattice problems in \(\ell_{p}\) norms. Zbl 1149.68039
Peikert, Chris
18
2008
Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022
Krause, Matthias; Pudlák, Pavel
18
1998
The complexity of matrix rank and feasible systems of linear equations. Zbl 0949.68071
Allender, Eric; Beals, Robert; Ogihara, Mitsunori
18
1999
A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Zbl 1286.68208
Seto, Kazuhisa; Tamaki, Suguru
18
2013
Disjointness is hard in the multiparty number-on-the-forehead model. Zbl 1213.68314
Lee, Troy; Shraibman, Adi
18
2009
Optimality of size-width tradeoffs for resolution. Zbl 1024.03012
Bonet, Maria Luisa; Galesi, Nicola
17
2001
Lower bounds for linear locally decodable codes and private information retrieval. Zbl 1113.68049
Goldreich, Oded; Karloff, Howard; Schulman, Leonard J.; Trevisan, Luca
17
2006
Symmetric alternation captures BPP. Zbl 0912.68054
Russell, Alexander; Sundaram, Ravi
17
1998
Toward a model for backtracking and dynamic programming. Zbl 1252.68130
Alekhnovich, Michael; Borodin, Allan; Buresh-Oppenheim, Joshua; Impagliazzo, Russell; Magen, Avner; Pitassi, Toniann
17
2011
The sum of \(D\) small-bias generators fools polynomials of degree \(D\). Zbl 1217.68157
Viola, Emanuele
17
2009
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Zbl 1082.14065
Grigoriev, Dima; Pasechnik, Dmitrii V.
16
2005
The alternation hierarchy for sublogarithmic space is infinite. Zbl 0796.68099
von Braunmühl, Burchard; Gengler, Romain; Rettinger, Robert
16
1993
On the complexity of simulating space-bounded quantum computations. Zbl 1068.68066
Watrous, John
16
2003
The complexity of constructing pseudorandom generators from hard functions. Zbl 1061.68077
Viola, Emanuele
16
2004
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
16
2006
On the complexity of computing Kronecker coefficients. Zbl 1367.05012
Pak, Igor; Panova, Greta
16
2017
DNF sparsification and a faster deterministic counting algorithm. Zbl 1286.68230
Gopalan, Parikshit; Meka, Raghu; Reingold, Omer
16
2013
The landscape of communication complexity classes. Zbl 1398.68180
Göös, Mika; Pitassi, Toniann; Watson, Thomas
16
2018
Approximation resistant predicates from pairwise independence. Zbl 1214.68172
Austrin, Per; Mossel, Elchanan
16
2009
A complexity gap for tree resolution. Zbl 0994.03005
Riis, Søren
15
2002
Graph isomorphism is low for PP. Zbl 0770.68055
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
15
1992
Decompositions of algebras over \(\mathbb{R}\) and \(\mathbb{C}\). Zbl 0774.68069
Eberly, Wayne
15
1991
Randomness in interactive proofs. Zbl 0802.68053
Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi
15
1993
Lower bounds for monotone span programs. Zbl 0870.68072
Beimel, Amos; Gál, Anna; Paterson, Mike
14
1997
\(\text{RL}\subseteq \text{SC}\). Zbl 0806.68043
Nisan, Noam
14
1994
Non-automatizability of bounded-depth Frege proofs. Zbl 1058.03063
Bonet, Maria Luisa; Domingo, Carlos; Gavaldà, Ricard; Maciel, Alexis; Pitassi, Toniann
14
2004
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
14
1995
More on average case vs approximation complexity. Zbl 1242.68109
Alekhnovich, Michael
14
2011
On vanishing of Kronecker coefficients. Zbl 1382.68093
Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael
14
2017
Communication complexity towards lower bounds on circuit depth. Zbl 1053.68048
Edmonds, Jeff; Impagliazzo, Russell; Rudich, Steven; Sgall, Jiří
13
2001
A characterization of span program size and improved lower bounds for monotone span programs. Zbl 1039.68051
Gàl, Anna
13
2001
Decomposition of algebras over finite fields and number fields. Zbl 0774.68068
Eberly, Wayne
13
1991
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
13
2005
Halfspace matrices. Zbl 1147.68027
Sherstov, Alexander A.
13
2008
Pseudorandomness for approximate counting and sampling. Zbl 1125.68058
Shaltiel, Ronen; Umans, Christopher
13
2006
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
13
2013
On approximate majority and probabilistic time. Zbl 1217.68101
Viola, Emanuele
13
2009
Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035
Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir
12
2015
Algorithmic properties of maximal orders in simple algebras over \(\mathbb{Q}\). Zbl 0787.16002
Rónyai, Lajos
12
1992
Existence and efficient construction of fast Fourier transforms on supersolvable groups. Zbl 0778.65092
Baum, Ulrich
12
1991
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Zbl 1085.68055
Gutfreund, Dan; Shaltiel, Ronen; Ta-Shma, Amnon
12
2003
Parameterized complexity of constraint satisfaction problems. Zbl 1085.68068
Marx, Dániel
12
2005
Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond. Zbl 07727626
Koiran, Pascal; Saha, Subhayan
2
2023
Rank and border rank of Kronecker powers of tensors and Strassen’s laser method. Zbl 1493.14088
Conner, Austin; Gesmundo, Fulvio; Landsberg, Joseph M.; Ventura, Emanuele
4
2022
The complexity of approximating the complex-valued Potts model. Zbl 07506814
Galanis, Andreas; Goldberg, Leslie Ann; Herrera-Poyatos, Andrés
1
2022
Computing zero-dimensional tropical varieties via projections. Zbl 07548100
Görlach, Paul; Ren, Yue; Zhang, Leon
1
2022
Quadratic lower bounds for algebraic branching programs and formulas. Zbl 07565467
Chatterjee, Prerona; Kumar, Mrinal; She, Adrian; Lee Volk, Ben
1
2022
Zeros and approximations of holant polynomials on the complex plane. Zbl 07581356
Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Göbel, Andreas; Lagodzinski, J. A. Gregor
1
2022
Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs. Zbl 1497.03066
Itsykson, Dmitry; Riazanov, Artur; Sagunov, Danil; Smirnov, Petr
3
2021
Lower bounds for matrix factorization. Zbl 07372271
Volk, Ben Lee; Kumar, Mrinal
2
2021
Smooth and strong PCPs. Zbl 1485.68101
Paradise, Orr
1
2021
Explicit list-decodable codes with optimal rate for computationally bounded channels. Zbl 1483.94076
Shaltiel, Ronen; Silbak, Jad
1
2021
The hardest halfspace. Zbl 1508.68122
Sherstov, Alexander A.
1
2021
Two-closures of supersolvable permutation groups in polynomial time. Zbl 1484.20002
Ponomarenko, Ilia; Vasil’ev, Andrey
4
2020
The computational complexity of plethysm coefficients. Zbl 1506.68031
Fischer, Nick; Ikenmeyer, Christian
1
2020
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs. Zbl 1435.68382
Ito, Hiro; Khoury, Areej; Newman, Ilan
1
2020
Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Zbl 1415.65098
Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen
8
2019
A quadratic lower bound for homogeneous algebraic branching programs. Zbl 1429.68072
Kumar, Mrinal
5
2019
Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\). Zbl 1425.68127
Göös, Mika; Kamath, Pritish; Pitassi, Toniann; Watson, Thomas
4
2019
Tensor surgery and tensor rank. Zbl 1414.05206
Christandl, Matthias; Zuiddam, Jeroen
3
2019
Simulation theorems via pseudo-random properties. Zbl 1496.68150
Chattopadhyay, Arkadev; Koucký, Michal; Loff, Bruno; Mukhopadhyay, Sagnik
3
2019
Improved bounds for quantified derandomization of constant-depth circuits and polynomials. Zbl 1425.68133
Tell, Roei
2
2019
Random resolution refutations. Zbl 1445.03063
Pudlák, Pavel; Thapen, Neil
1
2019
Vanishing of Littlewood-Richardson polynomials is in P. Zbl 1471.14100
Adve, Anshul; Robichaux, Colleen; Yong, Alexander
1
2019
Approximate nonnegative rank is equivalent to the smooth rectangle bound. Zbl 1423.68194
Kol, Gillat; Moran, Shay; Shpilka, Amir; Yehudayoff, Amir
1
2019
Depth-4 lower bounds, determinantal complexity: a unified approach. Zbl 1498.68124
Chillara, Suryajith; Mukhopadhyay, Partha
1
2019
Hierarchy theorems for testing properties in size-oblivious query complexity. Zbl 1494.68091
Goldreich, Oded
1
2019
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Zbl 1494.68082
Kayal, Neeraj; Nair, Vineet; Saha, Chandan
1
2019
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Zbl 1429.68079
Cai, Jin-Yi; Chen, Xi
1
2019
Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees. Zbl 1422.68086
Lagarde, Guillaume; Limaye, Nutan; Srinivasan, Srikanth
1
2019
Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
26
2018
The landscape of communication complexity classes. Zbl 1398.68180
Göös, Mika; Pitassi, Toniann; Watson, Thomas
16
2018
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
10
2018
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity. Zbl 1402.68073
Dinur, Irit; Meir, Or
6
2018
Non-interactive proofs of proximity. Zbl 1391.68098
Gur, Tom; Rothblum, Ron D.
6
2018
An adaptivity hierarchy theorem for property testing. Zbl 1403.68331
Canonne, Clément L.; Gur, Tom
5
2018
The average sensitivity of bounded-depth formulas. Zbl 1396.68050
Rossman, Benjamin
3
2018
Some observations on holographic algorithms. Zbl 1419.68211
Valiant, Leslie G.
3
2018
On space and depth in resolution. Zbl 06974168
Razborov, Alexander
3
2018
Local expanders. Zbl 1398.68164
Viola, Emanuele; Wigderson, Avi
2
2018
Matrix rigidity of random Toeplitz matrices. Zbl 1398.68237
Goldreich, Oded; Tal, Avishay
2
2018
On the hardness of the noncommutative determinant. Zbl 1390.68319
Arvind, V.; Srinivasan, Srikanth
2
2018
On semiring complexity of Schur polynomials. Zbl 1408.68072
Fomin, Sergey; Grigoriev, Dima; Nogneng, Dorian; Schost, Éric
1
2018
Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits. Zbl 1446.12001
Pandey, Anurag; Saxena, Nitin; Sinhababu, Amit
1
2018
Autoreducibility of NP-complete sets under strong hypotheses. Zbl 1390.68321
Hitchcock, John M.; Shafei, Hadi
1
2018
Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
30
2017
On the complexity of computing Kronecker coefficients. Zbl 1367.05012
Pak, Igor; Panova, Greta
16
2017
On vanishing of Kronecker coefficients. Zbl 1382.68093
Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael
14
2017
Graph isomorphism, color refinement, and compactness. Zbl 1379.05080
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
10
2017
Information-theoretic approximations of the nonnegative rank. Zbl 1381.94044
Braun, Gábor; Jain, Rahul; Lee, Troy; Pokutta, Sebastian
8
2017
On the structure of Boolean functions with small spectral norm. Zbl 1371.94704
Shpilka, Amir; Tal, Avishay; Volk, Ben lee
8
2017
The minimum oracle circuit size problem. Zbl 1408.68065
Allender, Eric; Holden, Dhiraj; Kabanets, Valentine
8
2017
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
8
2017
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Zbl 1378.68049
Doron, Dean; Sarid, Amir; Ta-Shma, Amnon
5
2017
Fourier concentration from shrinkage. Zbl 1371.68092
Impagliazzo, Russell; Kabanets, Valentine
4
2017
List-decoding Barnes-Wall lattices. Zbl 1405.94133
Grigorescu, Elena; Peikert, Chris
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
Sunflowers and testing triangle-freeness of functions. Zbl 1379.68340
Haviv, Ishay; Xie, Ning
3
2017
On the connection between interval size functions and path counting. Zbl 1401.68107
Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris
2
2017
Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Zbl 1382.68110
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin; Thierauf, Thomas
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
Low-degree test with polynomially small error. Zbl 1378.68052
Moshkovitz, Dana
1
2017
Tight size-degree bounds for sums-of-squares proofs. Zbl 1422.03125
Lauria, Massimo; Nordström, Jakob
1
2017
A dichotomy for real weighted Holant problems. Zbl 1336.68099
Huang, Sangxia; Lu, Pinyan
19
2016
Factors of low individual degree polynomials. Zbl 1345.68292
Oliveira, Rafael
6
2016
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Zbl 1345.68126
Applebaum, Benny; Artemenko, Sergei; Shaltiel, Ronen; Yang, Guang
5
2016
Combinatorial PCPs with short proofs. Zbl 1336.68090
Meir, Or
5
2016
Cryptographic hardness of random local functions. Survey. Zbl 1360.94293
Applebaum, Benny
5
2016
Lower bounds for depth-three arithmetic circuits with small bottom fanin. Zbl 1345.68161
Kayal, Neeraj; Saha, Chandan
3
2016
On the power of algebraic branching programs of width two. Zbl 1348.68061
Allender, Eric; Wang, Fengming
3
2016
Unprovable security of perfect NIZK and non-interactive non-malleable commitments. Zbl 1369.94562
Pass, Rafael
3
2016
Collapse of the hierarchy of constant-depth exact quantum circuits. Zbl 1353.68097
Takahashi, Yasuhiro; Tani, Seiichiro
3
2016
The complexity of estimating min-entropy. Zbl 1336.68109
Watson, Thomas
2
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
2
2016
Kolmogorov width of discrete linear spaces: an approach to matrix rigidity. Zbl 1344.68100
Samorodnitsky, Alex; Shkredov, Ilya; Yekhanin, Sergey
1
2016
Subexponential size hitting sets for bounded depth multilinear formulas. Zbl 1344.68090
Oliveira, Rafael; Shpilka, Amir; Volk, Ben Lee
1
2016
Relativizing small complexity classes and their theories. Zbl 1336.68084
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
1
2016
A counterexample to the chain rule for conditional HILL entropy. Zbl 1369.94550
Krenn, Stephan; Pietrzak, Krzysztof; Wadia, Akshay; Wichs, Daniel
1
2016
Testing list \(H\)-homomorphisms. Zbl 1353.68139
Yoshida, Yuichi
1
2016
The complexity of intersecting finite automata having few final states. Zbl 1353.68109
Blondin, Michael; Krebs, Andreas; McKenzie, Pierre
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
27
2015
Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035
Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir
12
2015
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
Grigoriev, Dima; Podolskii, Vladimir V.
11
2015
Quantum algorithms for learning symmetric juntas via the adversary bound. Zbl 1329.68115
Belovs, Aleksandrs
10
2015
A parallel repetition theorem for entangled projection games. Zbl 1329.68116
Dinur, Irit; Steurer, David; Vidick, Thomas
9
2015
Read-once polynomial identity testing. Zbl 1329.68147
Shpilka, Amir; Volkovich, Ilya
9
2015
Unifying known lower bounds via geometric complexity theory. Zbl 1329.68123
Grochow, Joshua A.
8
2015
Deterministic polynomial identity tests for multilinear bounded-read formulae. Zbl 1346.68105
Anderson, Matthew; van Melkebeek, Dieter; Volkovich, Ilya
6
2015
Composition of semi-LTCs by two-wise tensor products. Zbl 1336.94084
Ben-Sasson, Eli; Viderman, Michael
6
2015
Lower bounds for testing triangle-freeness in Boolean functions. Zbl 1332.68056
Bhattacharyya, Arnab; Xie, Ning
5
2015
Rank-one quantum games. Zbl 1328.81063
Cooney, T.; Junge, M.; Palazuelos, C.; Pérez-García, D.
5
2015
The NOF multiparty communication complexity of composed functions. Zbl 1329.68103
Ada, Anil; Chattopadhyay, Arkadev; Fawzi, Omar; Nguyen, Phuong
5
2015
On the complexity of inverting integer and polynomial matrices. Zbl 1333.68302
Storjohann, Arne
4
2015
Limits on alternation trading proofs for time-space lower bounds. Zbl 1338.68080
Buss, Samuel R.; Williams, Ryan
2
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
The correct exponent for the Gotsman-Linial conjecture. Zbl 1314.68138
Kane, Daniel M.
6
2014
On the power of non-adaptive learning graphs. Zbl 1314.68134
Belovs, Aleksandrs; Rosmanis, Ansis
6
2014
Using elimination theory to construct rigid matrices. Zbl 1366.68076
Kumar, Abhinav; Lokam, Satyanarayana V.; Patankar, Vijay M.; Sarma, M. N. Jayalal
5
2014
...and 330 more Documents
all top 5

Cited by 3,332 Authors

33 Goldreich, Oded
30 Cai, Jin-Yi
28 Arvind, Vikraman
25 Allender, Eric W.
23 Wigderson, Avi
22 Fortnow, Lance J.
22 Pitassi, Toniann
21 Servedio, Rocco A.
20 Applebaum, Benny
19 Chiesa, Alessandro
19 Ishai, Yuval
19 Mahajan, Meena
18 Grigor’ev, Dmitriĭ Yur’evich
17 Impagliazzo, Russell
17 Williams, Richard Ryan
16 Basu, Saugata
16 Buss, Samuel R.
16 Limaye, Nutan
16 Santhanam, Rahul
16 Srinivasan, Srikanth
15 Filmus, Yuval
15 Hemaspaandra, Lane A.
15 Kabanets, Valentine
15 Meir, Or
15 O’Donnell, Ryan
15 Schost, Éric
15 Yukna, Stasys P.
14 Buhrman, Harry
14 Chattopadhyay, Arkadev
14 Kumar, Mrinal
14 Shparlinski, Igor E.
14 Shpilka, Amir
14 Sudan, Madhu
13 Ben-Sasson, Eli
13 Beyersdorff, Olaf
13 Gál, Anna
13 Glaßer, Christian
13 Ivanyos, Gábor
13 Lovett, Shachar
13 Raghavendra Rao, B. V.
13 Sherstov, Alexander A.
12 Göös, Mika
12 Gur, Tom
12 Ikenmeyer, Christian
12 Koiran, Pascal
12 Makam, Visu
12 Mukhopadhyay, Partha
12 Saxena, Nitin
12 Shaltiel, Ronen
12 Viola, Emanuele
11 Atserias, Albert
11 Bürgisser, Peter
11 Dinur, Irit
11 Dvir, Zeev
11 Feige, Uriel
11 Guruswami, Venkatesan
11 Karpinski, Marek
11 Köbler, Johannes
11 Okhotin, Alexander
11 Pudlák, Pavel
11 Qiao, Youming
11 Rothblum, Ron D.
11 Saha, Chandan
11 Thaler, Justin
10 Beimel, Amos
10 Dal Lago, Ugo
10 Derksen, Harm
10 Galesi, Nicola
10 Itsykson, Dmitry M.
10 Kayal, Neeraj
10 Khot, Subhash Ajit
10 Krajíček, Jan
10 Lauria, Massimo
10 Lohrey, Markus
10 McKenzie, Pierre
10 Panova, Greta
10 Podol’skiĭ, Vladimir Vladimirovich
10 Raz, Ran
10 Thérien, Denis
10 van Melkebeek, Dieter
10 Vidick, Thomas
10 Vinodchandran, N. Variyam
10 von zur Gathen, Joachim
9 Beigel, Richard
9 Bogdanov, Andrej
9 Braverman, Mark
9 Bshouty, Nader H.
9 Galanis, Andreas
9 Håstad, Johan Torkel
9 Jansen, Maurice J.
9 Kurpisz, Adam
9 Martin, Barnaby D.
9 Micciancio, Daniele
9 Müller, Moritz
9 Pavan, Aduri
9 Razborov, Aleksandr Aleksandrovich
9 Santha, Miklos
9 Saptharishi, Ramprasad
9 Shinkar, Igor
9 Sun, Xiaoming
...and 3,232 more Authors
all top 5

Cited in 281 Journals

253 Theoretical Computer Science
194 Computational Complexity
130 Journal of Computer and System Sciences
112 SIAM Journal on Computing
93 Information and Computation
79 Information Processing Letters
78 Theory of Computing Systems
66 Algorithmica
49 Journal of Symbolic Computation
39 Discrete Applied Mathematics
32 Journal of Cryptology
31 Journal of Complexity
27 Mathematics of Computation
27 Annals of Pure and Applied Logic
25 Discrete Mathematics
24 Theory of Computing
23 Journal of Algebra
23 Designs, Codes and Cryptography
21 Linear Algebra and its Applications
18 SIAM Journal on Discrete Mathematics
18 Mathematical Programming. Series A. Series B
17 Discrete & Computational Geometry
17 Random Structures & Algorithms
17 International Journal of Foundations of Computer Science
17 Journal of Combinatorial Optimization
17 Foundations of Computational Mathematics
16 Combinatorica
15 Combinatorics, Probability and Computing
15 The Electronic Journal of Combinatorics
14 Quantum Information Processing
13 Journal of Pure and Applied Algebra
13 Journal of the ACM
12 The Journal of Symbolic Logic
12 Archive for Mathematical Logic
12 Logical Methods in Computer Science
11 Communications in Mathematical Physics
11 Advances in Mathematics
11 ACM Transactions on Computation Theory
10 Applicable Algebra in Engineering, Communication and Computing
9 Artificial Intelligence
9 Transactions of the American Mathematical Society
9 Discrete Analysis
8 Israel Journal of Mathematics
8 SIAM Journal on Optimization
8 Journal of Mathematical Sciences (New York)
8 The Bulletin of Symbolic Logic
7 Applied Mathematics and Computation
7 MSCS. Mathematical Structures in Computer Science
7 Discrete Optimization
7 Forum of Mathematics, Sigma
6 Physica A
6 The Annals of Probability
6 Journal of the American Mathematical Society
6 International Journal of Algebra and Computation
6 Bulletin of the American Mathematical Society. New Series
6 Annals of Mathematics. Second Series
6 RAIRO. Theoretical Informatics and Applications
6 ACM Transactions on Computational Logic
5 Journal of Mathematical Physics
5 Journal of Functional Analysis
5 Journal of Number Theory
5 Mathematics of Operations Research
5 Graphs and Combinatorics
5 Probability Theory and Related Fields
5 Neural Computation
5 Journal of Algebraic Combinatorics
5 Finite Fields and their Applications
5 Chicago Journal of Theoretical Computer Science
5 Journal of the European Mathematical Society (JEMS)
5 Lobachevskii Journal of Mathematics
5 Comptes Rendus. Mathématique. Académie des Sciences, Paris
5 SIAM Journal on Applied Algebra and Geometry
4 Computers & Mathematics with Applications
4 Linear and Multilinear Algebra
4 Computing
4 Journal of Combinatorial Theory. Series A
4 European Journal of Combinatorics
4 Advances in Applied Mathematics
4 Operations Research Letters
4 European Journal of Operational Research
4 The Journal of Fourier Analysis and Applications
4 LMS Journal of Computation and Mathematics
4 Journal of High Energy Physics
4 International Journal of Number Theory
4 Journal of Mathematical Cryptology
4 Algorithms
3 Communications in Algebra
3 Information Sciences
3 Journal of Combinatorial Theory. Series B
3 Mathematics and Computers in Simulation
3 Mathematical Systems Theory
3 Proceedings of the American Mathematical Society
3 Journal of Theoretical Probability
3 Applied Mathematics Letters
3 SIAM Journal on Matrix Analysis and Applications
3 Machine Learning
3 Japan Journal of Industrial and Applied Mathematics
3 Computational Geometry
3 Differential Geometry and its Applications
3 Distributed Computing
...and 181 more Journals
all top 5

Cited in 53 Fields

2,091 Computer science (68-XX)
490 Information and communication theory, circuits (94-XX)
401 Combinatorics (05-XX)
301 Mathematical logic and foundations (03-XX)
217 Operations research, mathematical programming (90-XX)
200 Number theory (11-XX)
147 Quantum theory (81-XX)
129 Algebraic geometry (14-XX)
105 Linear and multilinear algebra; matrix theory (15-XX)
90 Probability theory and stochastic processes (60-XX)
88 Group theory and generalizations (20-XX)
78 Commutative algebra (13-XX)
73 Order, lattices, ordered algebraic structures (06-XX)
73 Numerical analysis (65-XX)
62 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
59 Field theory and polynomials (12-XX)
47 Associative rings and algebras (16-XX)
36 Convex and discrete geometry (52-XX)
27 Statistics (62-XX)
27 Statistical mechanics, structure of matter (82-XX)
22 Functional analysis (46-XX)
13 Biology and other natural sciences (92-XX)
12 Nonassociative rings and algebras (17-XX)
12 Abstract harmonic analysis (43-XX)
11 Dynamical systems and ergodic theory (37-XX)
10 Differential geometry (53-XX)
8 General and overarching topics; collections (00-XX)
8 General algebraic systems (08-XX)
8 Real functions (26-XX)
8 Ordinary differential equations (34-XX)
7 Measure and integration (28-XX)
7 Operator theory (47-XX)
7 Geometry (51-XX)
6 History and biography (01-XX)
6 Category theory; homological algebra (18-XX)
6 Approximations and expansions (41-XX)
6 Systems theory; control (93-XX)
5 Harmonic analysis on Euclidean spaces (42-XX)
4 Functions of a complex variable (30-XX)
4 Partial differential equations (35-XX)
4 Manifolds and cell complexes (57-XX)
3 Topological groups, Lie groups (22-XX)
3 Potential theory (31-XX)
3 Calculus of variations and optimal control; optimization (49-XX)
3 Algebraic topology (55-XX)
2 \(K\)-theory (19-XX)
2 Difference and functional equations (39-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