## 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: 510 Publications (since 1991) References Indexed: 307 Publications with 9,011 References.
all top 5

### Latest Issues

 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) 3, No. 4 (1993) 3, No. 3 (1993) ...and 8 more Volumes
all top 5

### Authors

 13 Goldreich, Oded 13 Impagliazzo, Russell 13 Shpilka, Amir 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 Thierauf, Thomas 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 Goldberg, Leslie Ann 4 McKenzie, Pierre 4 Mix Barrington, David A. 4 Pavan, Aduri 4 Saks, Michael E. 4 Sgall, Jiří 4 Sudan, Madhu 4 Umans, Christopher 4 Vinodchandran, N. Variyam 4 Volk, Ben Lee 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 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 Kumar, Mrinal 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, Muli 3 Saha, Chandan 3 Schost, Éric 3 Shoup, Victor 3 Srinivasan, Srikanth 3 Ta-Shma, Amnon 3 Tiwari, Prasoon 3 Trevisan, Luca 3 Vorob’ëv, Nikolaĭ N. jun. 3 Watanabe, Osamu 3 Yukna, Stasys P. 2 Àlvarez, Carme 2 Ambainis, Andris ...and 543 more Authors
all top 5

### Fields

 490 Computer science (68-XX) 74 Information and communication theory, circuits (94-XX) 64 Mathematical logic and foundations (03-XX) 38 Combinatorics (05-XX) 36 Number theory (11-XX) 22 Linear and multilinear algebra; matrix theory (15-XX) 19 Algebraic geometry (14-XX) 19 Quantum theory (81-XX) 16 Commutative algebra (13-XX) 15 Order, lattices, ordered algebraic structures (06-XX) 14 General and overarching topics; collections (00-XX) 13 Operations research, mathematical programming (90-XX) 11 Field theory and polynomials (12-XX) 10 Group theory and generalizations (20-XX) 10 Numerical analysis (65-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Probability theory and stochastic processes (60-XX) 4 Associative rings and algebras (16-XX) 4 Approximations and expansions (41-XX) 3 History and biography (01-XX) 3 Convex and discrete geometry (52-XX) 2 General algebraic systems (08-XX) 2 Measure and integration (28-XX) 1 Real functions (26-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Operator theory (47-XX) 1 Manifolds and cell complexes (57-XX)

### Citations contained in zbMATH Open

414 Publications have been cited 3,686 times in 2,595 Documents Cited by Year
Derandomizing polynomial identity tests means proving circuit lower bounds. Zbl 1089.68042
Kabanets, Valentine; Impagliazzo, Russell
2004
A new recursion-theoretic characterization of the polytime functions. Zbl 0766.68037
Bellantoni, Stephen; Cook, Stephen
1992
Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041
Babai, László; Fortnow, Lance; Lund, Carsten
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
1997
On the degree of Boolean functions as real polynomials. Zbl 0829.68047
Nisan, Noam; Szegedy, Mario
1994
$$BPP$$ has subexponential time simulations unless $$EXPTIME$$ has publishable proofs. Zbl 0802.68054
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi
1993
Computing Frobenius maps and factoring polynomials. Zbl 0778.11076
von zur Gathen, Joachim; Shoup, Victor
1992
Majority gates vs. general weighted threshold gates. Zbl 0770.68054
Goldmann, Mikael; Håstad, Johan; Razborov, Alexander
1992
The hardness of approximation: Gap location. Zbl 0822.68052
Petrank, Erez
1994
On lower bounds for read-$$k$$-times branching programs. Zbl 0777.68043
Borodin, A.; Razborov, A.; Smolensky, R.
1993
On the hardness of approximating Multicut and Sparsest-Cut. Zbl 1132.68418
Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D.
2006
On the power of small-depth threshold circuits. Zbl 0774.68060
1991
On the complexity of approximating $$k$$-set packing. Zbl 1103.90105
Hazan, Elad; Safra, Shmuel; Schwartz, Oded
2006
Lower bounds on arithmetic circuits via partial derivatives. Zbl 0890.68074
Nisan, Noam; Wigderson, Avi
1997
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
1992
Exponential lower bounds for the pigeonhole principle. Zbl 0784.03034
Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell
1993
Computationally private randomizing polynomials and their applications. Zbl 1143.94009
Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal
2006
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Zbl 1133.68024
Micciancio, Daniele
2007
On ACC. Zbl 0835.68040
Beigel, Richard; Tarui, Jun
1994
Property testing lower bounds via communication complexity. Zbl 1253.68142
Blais, Eric; Brody, Joshua; Matulef, Kevin
2012
Lower bounds and separations for constant depth multilinear circuits. Zbl 1213.68319
Raz, Ran; Yehudayoff, Amir
2009
Perceptrons, PP, and the polynomial hierarchy. Zbl 0829.68059
Beigel, Richard
1994
Derandomized graph products. Zbl 0816.60070
Alon, Noga; Feige, Uriel; Wigderson, Avi; Zuckerman, David
1995
On randomized one-round communication complexity. Zbl 0942.68059
Kremer, Ilan; Nisan, Noam; Ron, Dana
1999
On the complexity of computing determinants. Zbl 1061.68185
Kaltofen, Erich; Villard, Gilles
2004
Depth-3 arithmetic circuits over fields of characteristic zero. Zbl 0998.68064
Shpilka, Amir; Wigderson, Avi
2001
Deterministic polynomial identity testing in non-commutative models. Zbl 1096.68070
Raz, Ran; Shpilka, Amir
2005
Representing Boolean functions as polynomials modulo composite numbers. Zbl 0829.68057
Barrington, David A. Mix; Beigel, Richard; Rudich, Steven
1994
Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
2017
Complexity of Positivstellensatz proofs for the knapsack. Zbl 0992.68077
Grigoriev, D.
2001
Super-logarithmic depth lower bounds via the direct sum in communication complexity. Zbl 0851.68034
Karchmer, Mauricio; Raz, Ran; Wigderson, Avi
1995
Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116
Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David
2015
Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129
Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří
1999
Quantum Arthur-Merlin games. Zbl 1085.68052
Watrous, Chris John
2005
Lower bounds for the polynomial calculus. Zbl 1026.03043
Razborov, Alexander A.
1998
Arithmetization: A new method in structural complexity theory. Zbl 0774.68040
Babai, László; Fortnow, Lance
1991
Cartesian graph factorization at logarithmic cost per edge. Zbl 0770.68064
Aurenhammer, F.; Hagauer, J.; Imrich, W.
1992
The complexity of membership problems for circuits over sets of natural numbers. Zbl 1133.68028
McKenzie, Pierre; Wagner, Klaus W.
2007
On the efficiency of effective Nullstellensätze. Zbl 0824.68051
Giusti, Marc; Heintz, Joos; Sabia, Juan
1993
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.
1997
Counting connected components of a semialgebraic set in subexponential time. Zbl 0900.68253
Grigor’ev, D. Yu.; Vorobjov, N. N. jun.
1992
Balancing syntactically multilinear arithmetic circuits. Zbl 1188.68367
Raz, Ran; Yehudayoff, Amir
2008
Derandomizing Arthur-Merlin games using hitting sets. Zbl 1085.68058
Miltersen, Peter Bro; Vinodchandran, N. V.
2005
On sunflowers and matrix multiplication. Zbl 1268.05223
Alon, Noga; Shpilka, Amir; Umans, Christopher
2013
Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182
Alekhnovich, Michael; Razborov, Alexander
2011
Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH. Zbl 1205.05240
Briand, Emmanuel; Orellana, Rosa; Rosas, Mercedes
2009
Pseudorandomness and average-case complexity via uniform reductions. Zbl 1133.68023
2007
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Zbl 0963.68082
Greenhill, Catherine
2000
Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022
Krause, Matthias; Pudlák, Pavel
1998
On interactive proofs with a laconic prover. Zbl 1053.68045
Goldreich, Oded; Vadhan, Salil; Wigderson, Avi
2002
Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
2018
Toward a model for backtracking and dynamic programming. Zbl 1252.68130
Alekhnovich, Michael; Borodin, Allan; Buresh-Oppenheim, Joshua; Impagliazzo, Russell; Magen, Avner; Pitassi, Toniann
2011
Lower bounds for linear locally decodable codes and private information retrieval. Zbl 1113.68049
Goldreich, Oded; Karloff, Howard; Schulman, Leonard J.; Trevisan, Luca
2006
Perfect parallel repetition theorem for quantum XOR proof systems. Zbl 1145.81017
Cleve, Richard; Slofstra, William; Unger, Falk; Upadhyay, Sarvagya
2008
Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Zbl 1082.14065
Grigoriev, Dima; Pasechnik, Dmitrii V.
2005
Disjointness is hard in the multiparty number-on-the-forehead model. Zbl 1213.68314
2009
Towards proving strong direct product theorems. Zbl 1084.68542
Shaltiel, Ronen
2003
Symmetric alternation captures BPP. Zbl 0912.68054
Russell, Alexander; Sundaram, Ravi
1998
$$NC^ 1$$: The automata-theoretic viewpoint. Zbl 0774.68048
McKenzie, Pierre; Péladeau, Pierre; Thérien, Denis
1991
The alternation hierarchy for sublogarithmic space is infinite. Zbl 0796.68099
von Braunmühl, Burchard; Gengler, Romain; Rettinger, Robert
1993
Graph isomorphism is low for PP. Zbl 0770.68055
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo
1992
Limits on the hardness of lattice problems in $$\ell_{p}$$ norms. Zbl 1149.68039
Peikert, Chris
2008
Optimality of size-width tradeoffs for resolution. Zbl 1024.03012
Bonet, Maria Luisa; Galesi, Nicola
2001
Extractors and rank extractors for polynomial sources. Zbl 1210.68136
Dvir, Zeev; Gabizon, Ariel; Wigderson, Avi
2009
Finding maximal orders in semisimple algebras over $$\mathbb{Q}$$. Zbl 0792.16020
Ivanyos, Gábor; Rónyai, Lajos
1993
A dichotomy for real weighted Holant problems. Zbl 1336.68099
Huang, Sangxia; Lu, Pinyan
2016
Polynomial identity testing for depth 3 circuits. Zbl 1173.94470
Kayal, Neeraj; Saxena, Nitin
2007
A complexity gap for tree resolution. Zbl 0994.03005
Riis, Søren
2002
The complexity of matrix rank and feasible systems of linear equations. Zbl 0949.68071
Allender, Eric; Beals, Robert; Ogihara, Mitsunori
1999
Approximation resistant predicates from pairwise independence. Zbl 1214.68172
Austrin, Per; Mossel, Elchanan
2009
Lipschitz continuous ordinary differential equations are polynomial-space complete. Zbl 1232.03031
Kawamura, Akitoshi
2010
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
2006
On the complexity of simulating space-bounded quantum computations. Zbl 1068.68066
Watrous, John
2003
The landscape of communication complexity classes. Zbl 1398.68180
Göös, Mika; Pitassi, Toniann; Watson, Thomas
2018
A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Zbl 1286.68208
Seto, Kazuhisa; Tamaki, Suguru
2013
Randomness in interactive proofs. Zbl 0802.68053
Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi
1993
Non-automatizability of bounded-depth Frege proofs. Zbl 1058.03063
Bonet, Maria Luisa; Domingo, Carlos; Gavaldà, Ricard; Maciel, Alexis; Pitassi, Toniann
2004
The complexity of constructing pseudorandom generators from hard functions. Zbl 1061.68077
Viola, Emanuele
2004
Lower bounds for monotone span programs. Zbl 0870.68072
Beimel, Amos; Gál, Anna; Paterson, Mike
1997
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
2005
More on average case vs approximation complexity. Zbl 1242.68109
Alekhnovich, Michael
2011
Halfspace matrices. Zbl 1147.68027
Sherstov, Alexander A.
2008
$$\text{RL}\subseteq \text{SC}$$. Zbl 0806.68043
Nisan, Noam
1994
Communication complexity towards lower bounds on circuit depth. Zbl 1053.68048
Edmonds, Jeff; Impagliazzo, Russell; Rudich, Steven; Sgall, Jiří
2001
A characterization of span program size and improved lower bounds for monotone span programs. Zbl 1039.68051
Gàl, Anna
2001
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
2013
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
1995
Decompositions of algebras over $$\mathbb{R}$$ and $$\mathbb{C}$$. Zbl 0774.68069
Eberly, Wayne
1991
Existence and efficient construction of fast Fourier transforms on supersolvable groups. Zbl 0778.65092
Baum, Ulrich
1991
DNF sparsification and a faster deterministic counting algorithm. Zbl 1286.68230
Gopalan, Parikshit; Meka, Raghu; Reingold, Omer
2013
When do extra majority gates help? Polylog$$(N)$$ majority gates are equivalent to one. Zbl 0829.68058
Beigel, Richard
1994
Counting curves and their projections. Zbl 0990.68642
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
1997
The sum of $$D$$ small-bias generators fools polynomials of degree $$D$$. Zbl 1217.68157
Viola, Emanuele
2009
Random CNF’s are hard for the polynomial calculus. Zbl 1216.03064
Ben-Sasson, Eli; Impagliazzo, Russell
2010
Pseudorandomness for approximate counting and sampling. Zbl 1125.68058
Shaltiel, Ronen; Umans, Christopher
2006
Efficient and optimal exponentiation in finite fields. Zbl 0788.68074
von zur Gathen, Joachim
1991
Decomposition of algebras over finite fields and number fields. Zbl 0774.68068
Eberly, Wayne
1991
Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035
Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir
2015
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
2018
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
2015
Rank and border rank of Kronecker powers of tensors and Strassen’s laser method. Zbl 07451421
Conner, Austin; Gesmundo, Fulvio; Landsberg, Joseph M.; Ventura, Emanuele
2022
The complexity of approximating the complex-valued Potts model. Zbl 07506814
Galanis, Andreas; Goldberg, Leslie Ann; Herrera-Poyatos, Andrés
2022
Lower bounds for matrix factorization. Zbl 07372271
Volk, Ben Lee; Kumar, Mrinal
2021
Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs. Zbl 07393895
Itsykson, Dmitry; Riazanov, Artur; Sagunov, Danil; Smirnov, Petr
2021
Smooth and strong PCPs. Zbl 1485.68101
2021
Two-closures of supersolvable permutation groups in polynomial time. Zbl 1484.20002
Ponomarenko, Ilia; Vasil&rsquo;ev, Andrey
2020
The computational complexity of plethysm coefficients. Zbl 07350836
Fischer, Nick; Ikenmeyer, Christian
2020
Query-to-communication lifting for $$\mathsf{P}^{\mathsf{NP}}$$. Zbl 1425.68127
Göös, Mika; Kamath, Pritish; Pitassi, Toniann; Watson, Thomas
2019
A quadratic lower bound for homogeneous algebraic branching programs. Zbl 1429.68072
Kumar, Mrinal
2019
Tensor surgery and tensor rank. Zbl 1414.05206
Christandl, Matthias; Zuiddam, Jeroen
2019
Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Zbl 1415.65098
Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen
2019
Simulation theorems via pseudo-random properties. Zbl 07145985
2019
Depth-4 lower bounds, determinantal complexity: a unified approach. Zbl 07145983
2019
Hierarchy theorems for testing properties in size-oblivious query complexity. Zbl 07145987
Goldreich, Oded
2019
Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees. Zbl 1422.68086
Lagarde, Guillaume; Limaye, Nutan; Srinivasan, Srikanth
2019
Vanishing of Littlewood-Richardson polynomials is in P. Zbl 1471.14100
Adve, Anshul; Robichaux, Colleen; Yong, Alexander
2019
Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
2018
The landscape of communication complexity classes. Zbl 1398.68180
Göös, Mika; Pitassi, Toniann; Watson, Thomas
2018
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
2018
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity. Zbl 1402.68073
Dinur, Irit; Meir, Or
2018
The average sensitivity of bounded-depth formulas. Zbl 1396.68050
Rossman, Benjamin
2018
Non-interactive proofs of proximity. Zbl 1391.68098
Gur, Tom; Rothblum, Ron D.
2018
An adaptivity hierarchy theorem for property testing. Zbl 1403.68331
Canonne, Clément L.; Gur, Tom
2018
Local expanders. Zbl 1398.68164
Viola, Emanuele; Wigderson, Avi
2018
Matrix rigidity of random Toeplitz matrices. Zbl 1398.68237
Goldreich, Oded; Tal, Avishay
2018
Some observations on holographic algorithms. Zbl 1419.68211
Valiant, Leslie G.
2018
On the hardness of the noncommutative determinant. Zbl 1390.68319
Arvind, V.; Srinivasan, Srikanth
2018
Autoreducibility of NP-complete sets under strong hypotheses. Zbl 1390.68321
2018
On space and depth in resolution. Zbl 06974168
Razborov, Alexander
2018
On semiring complexity of Schur polynomials. Zbl 1408.68072
Fomin, Sergey; Grigoriev, Dima; Nogneng, Dorian; Schost, Éric
2018
Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002
Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V.
2017
On vanishing of Kronecker coefficients. Zbl 1382.68093
Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael
2017
On the complexity of computing Kronecker coefficients. Zbl 1367.05012
Pak, Igor; Panova, Greta
2017
The minimum oracle circuit size problem. Zbl 1408.68065
Allender, Eric; Holden, Dhiraj; Kabanets, Valentine
2017
The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090
Goldberg, Leslie Ann; Guo, Heng
2017
Information-theoretic approximations of the nonnegative rank. Zbl 1381.94044
Braun, Gábor; Jain, Rahul; Lee, Troy; Pokutta, Sebastian
2017
Graph isomorphism, color refinement, and compactness. Zbl 1379.05080
Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg
2017
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Zbl 1378.68049
Doron, Dean; Sarid, Amir; Ta-Shma, Amnon
2017
On the structure of Boolean functions with small spectral norm. Zbl 1371.94704
Shpilka, Amir; Tal, Avishay; Volk, Ben lee
2017
Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games. Zbl 1371.68094
Aydınlıoğlu, Barış; van Melkebeek, Dieter
2017
Fourier concentration from shrinkage. Zbl 1371.68092
Impagliazzo, Russell; Kabanets, Valentine
2017
List-decoding Barnes-Wall lattices. Zbl 1405.94133
Grigorescu, Elena; Peikert, Chris
2017
On the connection between interval size functions and path counting. Zbl 1401.68107
Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris
2017
Sunflowers and testing triangle-freeness of functions. Zbl 1379.68340
Haviv, Ishay; Xie, Ning
2017
Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Zbl 1382.68110
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin; Thierauf, Thomas
2017
Block-symmetric polynomials correlate with parity better than symmetric. Zbl 1379.68153
Green, Frederic; Kreymer, Daniel; Viola, Emanuele
2017
Low-degree test with polynomially small error. Zbl 1378.68052
Moshkovitz, Dana
2017
Tight size-degree bounds for sums-of-squares proofs. Zbl 1422.03125
Lauria, Massimo; Nordström, Jakob
2017
Sparse affine-invariant linear codes are locally testable. Zbl 1381.94114
Ben-Sasson, Eli; Ron-Zewi, Noga; Sudan, Madhu
2017
Multipartite quantum correlation and communication complexities. Zbl 1371.68089
Jain, Rahul; Wei, Zhaohui; Yao, Penghui; Zhang, Shengyu
2017
A dichotomy for real weighted Holant problems. Zbl 1336.68099
Huang, Sangxia; Lu, Pinyan
2016
Cryptographic hardness of random local functions. Survey. Zbl 1360.94293
Applebaum, Benny
2016
Combinatorial PCPs with short proofs. Zbl 1336.68090
Meir, Or
2016
Unprovable security of perfect NIZK and non-interactive non-malleable commitments. Zbl 1369.94562
Pass, Rafael
2016
Collapse of the hierarchy of constant-depth exact quantum circuits. Zbl 1353.68097
Takahashi, Yasuhiro; Tani, Seiichiro
2016
Lower bounds for depth-three arithmetic circuits with small bottom fanin. Zbl 1345.68161
Kayal, Neeraj; Saha, Chandan
2016
Factors of low individual degree polynomials. Zbl 1345.68292
Oliveira, Rafael
2016
On the power of algebraic branching programs of width two. Zbl 1348.68061
Allender, Eric; Wang, Fengming
2016
Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Zbl 1345.68126
Applebaum, Benny; Artemenko, Sergei; Shaltiel, Ronen; Yang, Guang
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
2016
Testing list $$H$$-homomorphisms. Zbl 1353.68139
Yoshida, Yuichi
2016
The complexity of intersecting finite automata having few final states. Zbl 1353.68109
Blondin, Michael; Krebs, Andreas; McKenzie, Pierre
2016
Affine extractors over large fields with exponential error. Zbl 1419.11132
Bourgain, Jean; Dvir, Zeev; Leeman, Ethan
2016
The complexity of estimating min-entropy. Zbl 1336.68109
Watson, Thomas
2016
Relativizing small complexity classes and their theories. Zbl 1336.68084
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
2016
Kolmogorov width of discrete linear spaces: an approach to matrix rigidity. Zbl 1344.68100
Samorodnitsky, Alex; Shkredov, Ilya; Yekhanin, Sergey
2016
Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116
Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David
2015
Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035
Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir
2015
Complexity of tropical and MIN-plus linear prevarieties. Zbl 1326.15039
2015
A parallel repetition theorem for entangled projection games. Zbl 1329.68116
Dinur, Irit; Steurer, David; Vidick, Thomas
2015
Unifying known lower bounds via geometric complexity theory. Zbl 1329.68123
Grochow, Joshua A.
2015
Read-once polynomial identity testing. Zbl 1329.68147
Shpilka, Amir; Volkovich, Ilya
2015
Quantum algorithms for learning symmetric juntas via the adversary bound. Zbl 1329.68115
Belovs, Aleksandrs
2015
Deterministic polynomial identity tests for multilinear bounded-read formulae. Zbl 1346.68105
Anderson, Matthew; van Melkebeek, Dieter; Volkovich, Ilya
2015
Composition of semi-LTCs by two-wise tensor products. Zbl 1336.94084
Ben-Sasson, Eli; Viderman, Michael
2015
The NOF multiparty communication complexity of composed functions. Zbl 1329.68103
2015
Lower bounds for testing triangle-freeness in Boolean functions. Zbl 1332.68056
Bhattacharyya, Arnab; Xie, Ning
2015
On the complexity of inverting integer and polynomial matrices. Zbl 1333.68302
Storjohann, Arne
2015
Rank-one quantum games. Zbl 1328.81063
Cooney, T.; Junge, M.; Palazuelos, C.; Pérez-García, D.
2015
Limits on alternation trading proofs for time-space lower bounds. Zbl 1338.68080
Buss, Samuel R.; Williams, Ryan
2015
The remote set problem on lattices. Zbl 1332.68077
Haviv, Ishay
2015
On rigid matrices and $$U$$-polynomials. Zbl 1333.68120
Alon, Noga; Cohen, Gil
2015
On the power of non-adaptive learning graphs. Zbl 1314.68134
Belovs, Aleksandrs; Rosmanis, Ansis
2014
Using elimination theory to construct rigid matrices. Zbl 1366.68076
Kumar, Abhinav; Lokam, Satyanarayana V.; Patankar, Vijay M.; Sarma, M. N. Jayalal
2014
Randomness buys depth for approximate counting. Zbl 1318.68091
Viola, Emanuele
2014
On uniformity and circuit lower bounds. Zbl 1314.68139
Santhanam, Rahul; Williams, Ryan
2014
Random arithmetic formulas can be reconstructed efficiently. Zbl 1314.68390
Gupta, Ankit; Kayal, Neeraj; Qiao, Youming
2014
Variety evasive sets. Zbl 1308.68166
Dvir, Zeev; Kollár, János; Lovett, Shachar
2014
Short lists for shortest descriptions in short time. Zbl 1366.68103
Teutsch, Jason
2014
The correct exponent for the Gotsman-Linial conjecture. Zbl 1314.68138
Kane, Daniel M.
2014
Choosing, agreeing, and eliminating in communication complexity. Zbl 1366.68050
Beimel, Amos; Ben Daniel, Sebastian; Kushilevitz, Eyal; Weinreb, Enav
2014
An $$\mathsf{AC}^{1}$$-complete model checking problem for intuitionistic logic. Zbl 06374277
Mundhenk, Martin; Wei, Felix
2014
Combinatorial PCPs with efficient verifiers. Zbl 1318.68087
Meir, Or
2014
How low can approximate degree and quantum query complexity be for total Boolean functions? Zbl 1314.68133
Ambainis, Andris; De Wolf, Ronald
2014
Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. Zbl 1366.68070
Artemenko, Sergei; Shaltiel, Ronen
2014
On sunflowers and matrix multiplication. Zbl 1268.05223
Alon, Noga; Shpilka, Amir; Umans, Christopher
2013
A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Zbl 1286.68208
Seto, Kazuhisa; Tamaki, Suguru
2013
Complexity of solving tropical linear systems. Zbl 1282.68137
Grigoriev, Dima
2013
DNF sparsification and a faster deterministic counting algorithm. Zbl 1286.68230
Gopalan, Parikshit; Meka, Raghu; Reingold, Omer
2013
2-transitivity is insufficient for local testability. Zbl 1283.94130
Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu
2013
...and 314 more Documents
all top 5

### Cited by 3,012 Authors

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

### Cited in 261 Journals

 243 Theoretical Computer Science 182 Computational Complexity 127 Journal of Computer and System Sciences 109 SIAM Journal on Computing 90 Information and Computation 79 Information Processing Letters 74 Theory of Computing Systems 64 Algorithmica 45 Journal of Symbolic Computation 38 Discrete Applied Mathematics 31 Journal of Cryptology 27 Mathematics of Computation 27 Journal of Complexity 26 Annals of Pure and Applied Logic 25 Discrete Mathematics 21 Journal of Algebra 20 Designs, Codes and Cryptography 19 Linear Algebra and its Applications 17 Random Structures & Algorithms 17 International Journal of Foundations of Computer Science 17 Mathematical Programming. Series A. Series B 16 Combinatorica 16 Discrete & Computational Geometry 16 SIAM Journal on Discrete Mathematics 16 Journal of Combinatorial Optimization 16 Theory of Computing 15 Foundations of Computational Mathematics 13 The Electronic Journal of Combinatorics 13 Logical Methods in Computer Science 12 Journal of Pure and Applied Algebra 12 The Journal of Symbolic Logic 12 Combinatorics, Probability and Computing 11 Archive for Mathematical Logic 11 ACM Transactions on Computation Theory 10 Applicable Algebra in Engineering, Communication and Computing 9 Advances in Mathematics 9 Transactions of the American Mathematical Society 9 Journal of the ACM 9 Discrete Analysis 8 Artificial Intelligence 8 Communications in Mathematical Physics 8 SIAM Journal on Optimization 8 Journal of Mathematical Sciences (New York) 8 The Bulletin of Symbolic Logic 8 Quantum Information Processing 7 Israel Journal of Mathematics 7 Applied Mathematics and Computation 6 International Journal of Algebra and Computation 6 MSCS. Mathematical Structures in Computer Science 6 Bulletin of the American Mathematical Society. New Series 6 RAIRO. Theoretical Informatics and Applications 6 Discrete Optimization 5 Journal of Mathematical Physics 5 The Annals of Probability 5 Journal of Number Theory 5 Mathematics of Operations Research 5 Probability Theory and Related Fields 5 Journal of the American Mathematical Society 5 Neural Computation 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 Forum of Mathematics, Sigma 5 SIAM Journal on Applied Algebra and Geometry 4 Computers & Mathematics with Applications 4 Physica A 4 Computing 4 Journal of Combinatorial Theory. Series A 4 Advances in Applied Mathematics 4 Operations Research Letters 4 Graphs and Combinatorics 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 Journal of Mathematical Cryptology 4 Algorithms 3 Communications in Algebra 3 Linear and Multilinear Algebra 3 Information Sciences 3 Journal of Functional Analysis 3 Mathematics and Computers in Simulation 3 Mathematical Systems Theory 3 Proceedings of the American Mathematical Society 3 European Journal of Combinatorics 3 Journal of Theoretical Probability 3 Applied Mathematics Letters 3 Machine Learning 3 Japan Journal of Industrial and Applied Mathematics 3 Computational Geometry 3 Differential Geometry and its Applications 3 Distributed Computing 3 RAIRO. Informatique Théorique et Applications 3 Constraints 3 Natural Computing ...and 161 more Journals
all top 5

### Cited in 53 Fields

 1,873 Computer science (68-XX) 420 Information and communication theory, circuits (94-XX) 346 Combinatorics (05-XX) 268 Mathematical logic and foundations (03-XX) 193 Operations research, mathematical programming (90-XX) 176 Number theory (11-XX) 115 Quantum theory (81-XX) 112 Algebraic geometry (14-XX) 88 Linear and multilinear algebra; matrix theory (15-XX) 80 Probability theory and stochastic processes (60-XX) 77 Group theory and generalizations (20-XX) 72 Commutative algebra (13-XX) 69 Numerical analysis (65-XX) 57 Order, lattices, ordered algebraic structures (06-XX) 57 Field theory and polynomials (12-XX) 55 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 42 Associative rings and algebras (16-XX) 32 Convex and discrete geometry (52-XX) 25 Statistics (62-XX) 22 Statistical mechanics, structure of matter (82-XX) 19 Functional analysis (46-XX) 12 Nonassociative rings and algebras (17-XX) 11 Abstract harmonic analysis (43-XX) 11 Biology and other natural sciences (92-XX) 10 Dynamical systems and ergodic theory (37-XX) 10 Differential geometry (53-XX) 8 General algebraic systems (08-XX) 8 Real functions (26-XX) 8 Ordinary differential equations (34-XX) 7 General and overarching topics; collections (00-XX) 7 Measure and integration (28-XX) 7 Approximations and expansions (41-XX) 6 Category theory; homological algebra (18-XX) 6 Operator theory (47-XX) 6 Geometry (51-XX) 6 Systems theory; control (93-XX) 5 Harmonic analysis on Euclidean spaces (42-XX) 4 History and biography (01-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)