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: 542 Publications (since 1991) References Indexed: 338 Publications with 10,156 References. all top 5 Latest Issues 33, No. 2 (2024) 33, No. 1 (2024) 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) ...and 12 more Volumes all top 5 Authors 14 Goldreich, Oded 14 Impagliazzo, Russell 13 Pitassi, Toniann 13 Shpilka, Amir 12 Shaltiel, Ronen 11 Fortnow, Lance J. 11 Grigor’ev, Dmitriĭ Yur’evich 11 Wigderson, Avi 10 Raz, Ran 9 Kabanets, Valentine 9 Meir, Or 9 Watson, Thomas 8 Allender, Eric W. 8 Razborov, Aleksandr Aleksandrovich 8 Saxena, Nitin 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 Kumar, Mrinal 6 Nisan, Noam 6 Shparlinski, Igor E. 6 Thierauf, Thomas 6 Volk, Ben Lee 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 Lee, Troy 5 Lovett, Shachar 5 Lund, Carsten 5 Pudlák, Pavel 5 Qiao, Youming 5 Sherstov, Alexander A. 5 Sudan, Madhu 5 Vadhan, Salil P. 5 von zur Gathen, Joachim 5 Williams, Richard Ryan 5 Yehudayoff, Amir 4 Arvind, Vikraman 4 Babai, László 4 Bshouty, Nader H. 4 Bürgisser, Peter 4 Damm, Carsten 4 Goldberg, Leslie Ann 4 Ishai, Yuval 4 Koiran, Pascal 4 McKenzie, Pierre 4 Mix Barrington, David A. 4 Pavan, Aduri 4 Ron, Dana 4 Saks, Michael E. 4 Sgall, Jiří 4 Srinivasan, Srikanth 4 Ta-Shma, Amnon 4 Umans, Christopher 4 Vinodchandran, N. Variyam 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 Ivanyos, Gábor 3 Kindler, Guy 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 Nordström, Jakob 3 Paterson, Mike S. 3 Rudich, Steven 3 Safra, Muli 3 Saha, Chandan 3 Schost, Éric 3 Shoup, Victor 3 Tal, Avishay ...and 587 more Authors all top 5 Fields 520 Computer science (68-XX) 76 Information and communication theory, circuits (94-XX) 68 Mathematical logic and foundations (03-XX) 43 Combinatorics (05-XX) 38 Number theory (11-XX) 24 Linear and multilinear algebra; matrix theory (15-XX) 21 Algebraic geometry (14-XX) 20 Quantum theory (81-XX) 18 Commutative algebra (13-XX) 15 Order, lattices, ordered algebraic structures (06-XX) 15 Operations research, mathematical programming (90-XX) 14 General and overarching topics; collections (00-XX) 14 Field theory and polynomials (12-XX) 12 Group theory and generalizations (20-XX) 10 Numerical analysis (65-XX) 8 Probability theory and stochastic processes (60-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Associative rings and algebras (16-XX) 4 Approximations and expansions (41-XX) 3 History and biography (01-XX) 3 General algebraic systems (08-XX) 3 Convex and discrete geometry (52-XX) 2 Measure and integration (28-XX) 2 Statistical mechanics, structure of matter (82-XX) 1 Real functions (26-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Difference and functional equations (39-XX) 1 Operator theory (47-XX) 1 Manifolds and cell complexes (57-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 448 Publications have been cited 5,654 times in 3,749 Documents Cited by ▼ Year ▼ Non-deterministic exponential time has two-prover interactive protocols. Zbl 0774.68041 Babai, László; Fortnow, Lance; Lund, Carsten 151 1991 A new recursion-theoretic characterization of the polytime functions. Zbl 0766.68037 Bellantoni, Stephen; Cook, Stephen 141 1992 Derandomizing polynomial identity tests means proving circuit lower bounds. Zbl 1089.68042 Kabanets, Valentine; Impagliazzo, Russell 134 2004 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 130 1997 On the degree of Boolean functions as real polynomials. Zbl 0829.68047 Nisan, Noam; Szegedy, Mario 112 1994 \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs. Zbl 0802.68054 Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi 93 1993 Computing Frobenius maps and factoring polynomials. Zbl 0778.11076 von zur Gathen, Joachim; Shoup, Victor 72 1992 Lower bounds on arithmetic circuits via partial derivatives. Zbl 0890.68074 Nisan, Noam; Wigderson, Avi 71 1997 Majority gates vs. general weighted threshold gates. Zbl 0770.68054 Goldmann, Mikael; Håstad, Johan; Razborov, Alexander 70 1992 Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Zbl 1133.68024 Micciancio, Daniele 67 2007 On the power of small-depth threshold circuits. Zbl 0774.68060 Håstad, Johan; Goldmann, Mikael 66 1991 The hardness of approximation: Gap location. Zbl 0822.68052 Petrank, Erez 62 1994 Exponential lower bounds for the pigeonhole principle. Zbl 0784.03034 Pitassi, Toniann; Beame, Paul; Impagliazzo, Russell 60 1993 On the hardness of approximating Multicut and Sparsest-Cut. Zbl 1132.68418 Chawla, Shuchi; Krauthgamer, Robert; Kumar, Ravi; Rabani, Yuval; Sivakumar, D. 60 2006 On the complexity of computing determinants. Zbl 1061.68185 Kaltofen, Erich; Villard, Gilles 59 2004 On lower bounds for read-\(k\)-times branching programs. Zbl 0777.68043 Borodin, A.; Razborov, A.; Smolensky, R. 58 1993 On the complexity of approximating \(k\)-set packing. Zbl 1103.90105 Hazan, Elad; Safra, Shmuel; Schwartz, Oded 56 2006 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 54 1992 Quantum Arthur-Merlin games. Zbl 1085.68052 Watrous, Chris John 54 2005 On ACC. Zbl 0835.68040 Beigel, Richard; Tarui, Jun 50 1994 Computationally private randomizing polynomials and their applications. Zbl 1143.94009 Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal 50 2006 Lower bounds and separations for constant depth multilinear circuits. Zbl 1213.68319 Raz, Ran; Yehudayoff, Amir 48 2009 Lower bounds for the polynomial calculus and the Gröbner basis algorithm. Zbl 0946.68129 Impagliazzo, Russell; Pudlák, Pavel; Sgall, Jiří 46 1999 Property testing lower bounds via communication complexity. Zbl 1253.68142 Blais, Eric; Brody, Joshua; Matulef, Kevin 45 2012 Complexity of Positivstellensatz proofs for the knapsack. Zbl 0992.68077 Grigoriev, D. 44 2001 On randomized one-round communication complexity. Zbl 0942.68059 Kremer, Ilan; Nisan, Noam; Ron, Dana 44 1999 Pseudorandomness and average-case complexity via uniform reductions. Zbl 1133.68023 Trevisan, Luca; Vadhan, Salil 43 2007 Deterministic polynomial identity testing in non-commutative models. Zbl 1096.68070 Raz, Ran; Shpilka, Amir 43 2005 Lower bounds for the polynomial calculus. Zbl 1026.03043 Razborov, Alexander A. 39 1998 Derandomized graph products. Zbl 0816.60070 Alon, Noga; Feige, Uriel; Wigderson, Avi; Zuckerman, David 38 1995 Depth-3 arithmetic circuits over fields of characteristic zero. Zbl 0998.68064 Shpilka, Amir; Wigderson, Avi 38 2001 On interactive proofs with a laconic prover. Zbl 1053.68045 Goldreich, Oded; Vadhan, Salil; Wigderson, Avi 36 2002 Non-commutative Edmonds’ problem and matrix semi-invariants. Zbl 1421.13002 Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V. 36 2017 Derandomizing Arthur-Merlin games using hitting sets. Zbl 1085.68058 Miltersen, Peter Bro; Vinodchandran, N. V. 35 2005 Perceptrons, PP, and the polynomial hierarchy. Zbl 0829.68059 Beigel, Richard 34 1994 Super-logarithmic depth lower bounds via the direct sum in communication complexity. Zbl 0851.68034 Karchmer, Mauricio; Raz, Ran; Wigderson, Avi 34 1995 Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116 Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David 34 2015 Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197 Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V. 34 2018 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. 32 1997 Representing Boolean functions as polynomials modulo composite numbers. Zbl 0829.68057 Barrington, David A. Mix; Beigel, Richard; Rudich, Steven 31 1994 Counting connected components of a semialgebraic set in subexponential time. Zbl 0900.68253 Grigor’ev, D. Yu.; Vorobjov, N. N. jun. 31 1992 Satisfiability, branch-width and Tseitin tautologies. Zbl 1243.68182 Alekhnovich, Michael; Razborov, Alexander 29 2011 Reduced Kronecker coefficients and counter-examples to Mulmuley’s strong saturation conjecture SH. Zbl 1205.05240 Briand, Emmanuel; Orellana, Rosa; Rosas, Mercedes 29 2009 Balancing syntactically multilinear arithmetic circuits. Zbl 1188.68367 Raz, Ran; Yehudayoff, Amir 29 2008 The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Zbl 0963.68082 Greenhill, Catherine 28 2000 Approximation resistant predicates from pairwise independence. Zbl 1214.68172 Austrin, Per; Mossel, Elchanan 28 2009 DNF sparsification and a faster deterministic counting algorithm. Zbl 1286.68230 Gopalan, Parikshit; Meka, Raghu; Reingold, Omer 28 2013 On sunflowers and matrix multiplication. Zbl 1268.05223 Alon, Noga; Shpilka, Amir; Umans, Christopher 27 2013 The complexity of constructing pseudorandom generators from hard functions. Zbl 1061.68077 Viola, Emanuele 26 2004 Polynomial identity testing for depth 3 circuits. Zbl 1173.94470 Kayal, Neeraj; Saxena, Nitin 26 2007 Disjointness is hard in the multiparty number-on-the-forehead model. Zbl 1213.68314 Lee, Troy; Shraibman, Adi 26 2009 Extractors and rank extractors for polynomial sources. Zbl 1210.68136 Dvir, Zeev; Gabizon, Ariel; Wigderson, Avi 26 2009 On the efficiency of effective Nullstellensätze. Zbl 0824.68051 Giusti, Marc; Heintz, Joos; Sabia, Juan 25 1993 Towards proving strong direct product theorems. Zbl 1084.68542 Shaltiel, Ronen 25 2003 On vanishing of Kronecker coefficients. Zbl 1382.68093 Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael 25 2017 A dichotomy for real weighted Holant problems. Zbl 1336.68099 Huang, Sangxia; Lu, Pinyan 24 2016 The sum of \(D\) small-bias generators fools polynomials of degree \(D\). Zbl 1217.68157 Viola, Emanuele 24 2009 Limits on the hardness of lattice problems in \(\ell_{p}\) norms. Zbl 1149.68039 Peikert, Chris 24 2008 Cartesian graph factorization at logarithmic cost per edge. Zbl 0770.68064 Aurenhammer, F.; Hagauer, J.; Imrich, W. 23 1992 Arithmetization: A new method in structural complexity theory. Zbl 0774.68040 Babai, László; Fortnow, Lance 23 1991 The complexity of membership problems for circuits over sets of natural numbers. Zbl 1133.68028 McKenzie, Pierre; Wagner, Klaus W. 23 2007 Halfspace matrices. Zbl 1147.68027 Sherstov, Alexander A. 23 2008 Perfect parallel repetition theorem for quantum XOR proof systems. Zbl 1145.81017 Cleve, Richard; Slofstra, William; Unger, Falk; Upadhyay, Sarvagya 23 2008 Computing Boolean functions by polynomials and threshold circuits. Zbl 0936.94022 Krause, Matthias; Pudlák, Pavel 22 1998 On the complexity of computing Kronecker coefficients. Zbl 1367.05012 Pak, Igor; Panova, Greta 22 2017 Symmetric alternation captures BPP. Zbl 0912.68054 Russell, Alexander; Sundaram, Ravi 21 1998 The complexity of matrix rank and feasible systems of linear equations. Zbl 0949.68071 Allender, Eric; Beals, Robert; Ogihara, Mitsunori 21 1999 Optimality of size-width tradeoffs for resolution. Zbl 1024.03012 Bonet, Maria Luisa; Galesi, Nicola 21 2001 \(NC^ 1\): The automata-theoretic viewpoint. Zbl 0774.68048 McKenzie, Pierre; Péladeau, Pierre; Thérien, Denis 21 1991 Finding maximal orders in semisimple algebras over \(\mathbb{Q}\). Zbl 0792.16020 Ivanyos, Gábor; Rónyai, Lajos 21 1993 Lower bounds for linear locally decodable codes and private information retrieval. Zbl 1113.68049 Goldreich, Oded; Karloff, Howard; Schulman, Leonard J.; Trevisan, Luca 21 2006 Lipschitz continuous ordinary differential equations are polynomial-space complete. Zbl 1232.03031 Kawamura, Akitoshi 21 2010 A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Zbl 1286.68208 Seto, Kazuhisa; Tamaki, Suguru 21 2013 Top-down lower bounds for depth-three circuits. Zbl 0838.68056 Håstad, Johan; Jukna, S.; Pudlák, P. 20 1995 \(\text{RL}\subseteq \text{SC}\). Zbl 0806.68043 Nisan, Noam 20 1994 On approximate majority and probabilistic time. Zbl 1217.68101 Viola, Emanuele 20 2009 Pseudorandomness for approximate counting and sampling. Zbl 1125.68058 Shaltiel, Ronen; Umans, Christopher 19 2006 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 19 2006 Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. Zbl 1082.14065 Grigoriev, Dima; Pasechnik, Dmitrii V. 19 2005 More on average case vs approximation complexity. Zbl 1242.68109 Alekhnovich, Michael 19 2011 Toward a model for backtracking and dynamic programming. Zbl 1252.68130 Alekhnovich, Michael; Borodin, Allan; Buresh-Oppenheim, Joshua; Impagliazzo, Russell; Magen, Avner; Pitassi, Toniann 19 2011 On the security of Goldreich’s one-way function. Zbl 1280.68092 Bogdanov, Andrej; Qiao, Youming 19 2012 The landscape of communication complexity classes. Zbl 1398.68180 Göös, Mika; Pitassi, Toniann; Watson, Thomas 19 2018 On the complexity of simulating space-bounded quantum computations. Zbl 1068.68066 Watrous, John 19 2003 The complexity of the covering radius problem. Zbl 1085.68063 Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded 19 2005 Lower bounds for monotone span programs. Zbl 0870.68072 Beimel, Amos; Gál, Anna; Paterson, Mike 18 1997 Non-automatizability of bounded-depth Frege proofs. Zbl 1058.03063 Bonet, Maria Luisa; Domingo, Carlos; Gavaldà, Ricard; Maciel, Alexis; Pitassi, Toniann 18 2004 Graph isomorphism is low for PP. Zbl 0770.68055 Köbler, Johannes; Schöning, Uwe; Torán, Jacobo 18 1992 Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035 Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir 18 2015 Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Zbl 1085.68055 Gutfreund, Dan; Shaltiel, Ronen; Ta-Shma, Amnon 18 2003 On pseudorandom generators with linear stretch in \(\mathrm{NC}^{0}\). Zbl 1242.94016 Applebaum, Benny; Ishai, Yuval; Kushilevitz, Eyal 18 2008 When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one. Zbl 0829.68058 Beigel, Richard 17 1994 Randomness in interactive proofs. Zbl 0802.68053 Bellare, Mihir; Goldreich, Oded; Goldwasser, Shafi 17 1993 Communication complexity towards lower bounds on circuit depth. Zbl 1053.68048 Edmonds, Jeff; Impagliazzo, Russell; Rudich, Steven; Sgall, Jiří 17 2001 Decompositions of algebras over \(\mathbb{R}\) and \(\mathbb{C}\). Zbl 0774.68069 Eberly, Wayne 17 1991 Every linear threshold function has a low-weight approximator. Zbl 1128.68043 Servedio, Rocco A. 17 2007 The alternation hierarchy for sublogarithmic space is infinite. Zbl 0796.68099 von Braunmühl, Burchard; Gengler, Romain; Rettinger, Robert 16 1993 A complexity gap for tree resolution. Zbl 0994.03005 Riis, Søren 16 2002 A characterization of span program size and improved lower bounds for monotone span programs. Zbl 1039.68051 Gàl, Anna 16 2001 Homogeneous formulas and symmetric polynomials. Zbl 1233.68230 Hrubeš, Pavel; Yehudayoff, Amir 16 2011 Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond. Zbl 1541.14083 Koiran, Pascal; Saha, Subhayan 3 2023 A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory. Zbl 07709619 Cai, Jin-Yi; Fu, Zhiguo; Girstmair, Kurt; Kowalczyk, Michael 2 2023 A lower bound on the complexity of testing grained distributions. Zbl 07773324 Goldreich, Oded; Ron, Dana 1 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 9 2022 Computing zero-dimensional tropical varieties via projections. Zbl 1535.14142 Görlach, Paul; Ren, Yue; Zhang, Leon 4 2022 Zeros and approximations of Holant polynomials on the complex plane. Zbl 1547.68852 Casel, Katrin; Fischbeck, Philipp; Friedrich, Tobias; Göbel, Andreas; Lagodzinski, J. A. Gregor 3 2022 The complexity of finding fair independent sets in cycles. Zbl 07605017 Haviv, Ishay 3 2022 A cost-scaling algorithm for computing the degree of determinants. Zbl 1492.90148 Hirai, Hiroshi; Ikeda, Motoki 3 2022 Quadratic lower bounds for algebraic branching programs and formulas. Zbl 1547.68202 Chatterjee, Prerona; Kumar, Mrinal; She, Adrian; Lee Volk, Ben 3 2022 The complexity of approximating the complex-valued Potts model. Zbl 1542.68110 Galanis, Andreas; Goldberg, Leslie Ann; Herrera-Poyatos, Andrés 3 2022 A lower bound on determinantal complexity. Zbl 07605015 Kumar, Mrinal; Volk, Ben Lee 1 2022 Resolution with counting: dag-like lower bounds and different moduli. Zbl 1535.03276 Part, Fedor; Tzameret, Iddo 5 2021 The hardest halfspace. Zbl 1508.68122 Sherstov, Alexander A. 4 2021 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 4 2021 Lower bounds for matrix factorization. Zbl 1518.68097 Volk, Ben Lee; Kumar, Mrinal 4 2021 Smooth and strong PCPs. Zbl 1485.68101 Paradise, Orr 3 2021 Explicit list-decodable codes with optimal rate for computationally bounded channels. Zbl 1483.94076 Shaltiel, Ronen; Silbak, Jad 2 2021 Nullstellensatz size-degree trade-offs from reversible pebbling. Zbl 1522.03319 De Rezende, Susanna F.; Meir, Or; Nordström, Jakob; Robere, Robert 2 2021 Correction to: “Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs”. Zbl 1508.03090 Itsykson, Dmitry; Riazanov, Artur; Sagunov, Danil; Smirnov, Petr 1 2021 Nondeterministic and randomized Boolean hierarchies in communication complexity. Zbl 1522.68229 Pitassi, Toniann; Shirley, Morgan; Watson, Thomas 1 2021 Blackbox identity testing for sum of special ROABPs and its border class. Zbl 1522.68239 Bisht, Pranav; Saxena, Nitin 1 2021 Lower bounds for arithmetic circuits via the Hankel matrix. Zbl 1519.68079 Fijalkow, Nathanaël; Lagarde, Guillaume; Ohlmann, Pierre; Serre, Olivier 1 2021 Two-closures of supersolvable permutation groups in polynomial time. Zbl 1484.20002 Ponomarenko, Ilia; Vasil’ev, Andrey 7 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 4 2020 On \(\epsilon\)-sensitive monotone computations. Zbl 1461.68084 Hrubeš, Pavel 4 2020 The computational complexity of plethysm coefficients. Zbl 1506.68031 Fischer, Nick; Ikenmeyer, Christian 4 2020 Linear matroid intersection is in quasi-NC. Zbl 1468.90150 Gurjar, Rohit; Thierauf, Thomas 1 2020 Asymptotic tensor rank of graph tensors: beyond matrix multiplication. Zbl 1415.65098 Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen 9 2019 A quadratic lower bound for homogeneous algebraic branching programs. Zbl 1429.68072 Kumar, Mrinal 8 2019 Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\). Zbl 1425.68127 Göös, Mika; Kamath, Pritish; Pitassi, Toniann; Watson, Thomas 8 2019 Improved bounds for quantified derandomization of constant-depth circuits and polynomials. Zbl 1425.68133 Tell, Roei 7 2019 Simulation theorems via pseudo-random properties. Zbl 1496.68150 Chattopadhyay, Arkadev; Koucký, Michal; Loff, Bruno; Mukhopadhyay, Sagnik 6 2019 Tensor surgery and tensor rank. Zbl 1414.05206 Christandl, Matthias; Zuiddam, Jeroen 3 2019 Random resolution refutations. Zbl 1445.03063 Pudlák, Pavel; Thapen, Neil 3 2019 Average-case linear matrix factorization and reconstruction of low width algebraic branching programs. Zbl 1494.68082 Kayal, Neeraj; Nair, Vineet; Saha, Chandan 3 2019 A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights. Zbl 1429.68079 Cai, Jin-Yi; Chen, Xi 2 2019 Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees. Zbl 1422.68086 Lagarde, Guillaume; Limaye, Nutan; Srinivasan, Srikanth 2 2019 Approximate nonnegative rank is equivalent to the smooth rectangle bound. Zbl 1423.68194 Kol, Gillat; Moran, Shay; Shpilka, Amir; Yehudayoff, Amir 1 2019 Prediction from partial information and hindsight, with application to circuit lower bounds. Zbl 1425.68128 Meir, Or; Wigderson, Avi 1 2019 Vanishing of Littlewood-Richardson polynomials is in P. Zbl 1471.14100 Adve, Anshul; Robichaux, Colleen; Yong, Alexander 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 Constructive non-commutative rank computation is in deterministic polynomial time. Zbl 1402.68197 Ivanyos, Gábor; Qiao, Youming; Subrahmanyam, K. V. 34 2018 The landscape of communication complexity classes. Zbl 1398.68180 Göös, Mika; Pitassi, Toniann; Watson, Thomas 19 2018 Non-interactive proofs of proximity. Zbl 1391.68098 Gur, Tom; Rothblum, Ron D. 10 2018 Short lists with short programs in short time. Zbl 1390.68356 Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius 10 2018 An adaptivity hierarchy theorem for property testing. Zbl 1403.68331 Canonne, Clément L.; Gur, Tom 9 2018 Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity. Zbl 1402.68073 Dinur, Irit; Meir, Or 7 2018 On space and depth in resolution. Zbl 1522.03322 Razborov, Alexander 5 2018 The average sensitivity of bounded-depth formulas. Zbl 1396.68050 Rossman, Benjamin 5 2018 Some observations on holographic algorithms. Zbl 1419.68211 Valiant, Leslie G. 4 2018 Matrix rigidity of random Toeplitz matrices. Zbl 1398.68237 Goldreich, Oded; Tal, Avishay 4 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 3 2018 Local expanders. Zbl 1398.68164 Viola, Emanuele; Wigderson, Avi 3 2018 On semiring complexity of Schur polynomials. Zbl 1408.68072 Fomin, Sergey; Grigoriev, Dima; Nogneng, Dorian; Schost, Éric 2 2018 On the hardness of the noncommutative determinant. Zbl 1390.68319 Arvind, V.; Srinivasan, Srikanth 2 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. 36 2017 On vanishing of Kronecker coefficients. Zbl 1382.68093 Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael 25 2017 On the complexity of computing Kronecker coefficients. Zbl 1367.05012 Pak, Igor; Panova, Greta 22 2017 The minimum oracle circuit size problem. Zbl 1408.68065 Allender, Eric; Holden, Dhiraj; Kabanets, Valentine 14 2017 Graph isomorphism, color refinement, and compactness. Zbl 1379.05080 Arvind, V.; Köbler, Johannes; Rattan, Gaurav; Verbitsky, Oleg 12 2017 The complexity of approximating complex-valued Ising and Tutte partition functions. Zbl 1382.68090 Goldberg, Leslie Ann; Guo, Heng 11 2017 On the structure of Boolean functions with small spectral norm. Zbl 1371.94704 Shpilka, Amir; Tal, Avishay; Volk, Ben lee 10 2017 On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Zbl 1378.68049 Doron, Dean; Sarid, Amir; Ta-Shma, Amnon 9 2017 Information-theoretic approximations of the nonnegative rank. Zbl 1381.94044 Braun, Gábor; Jain, Rahul; Lee, Troy; Pokutta, Sebastian 8 2017 Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. Zbl 1382.68110 Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin; Thierauf, Thomas 7 2017 List-decoding Barnes-Wall lattices. Zbl 1405.94133 Grigorescu, Elena; Peikert, Chris 6 2017 Tight size-degree bounds for sums-of-squares proofs. Zbl 1422.03125 Lauria, Massimo; Nordström, Jakob 6 2017 Sunflowers and testing triangle-freeness of functions. Zbl 1379.68340 Haviv, Ishay; Xie, Ning 5 2017 Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games. Zbl 1371.68094 Aydınlıoğlu, Barış; van Melkebeek, Dieter 4 2017 Fourier concentration from shrinkage. Zbl 1371.68092 Impagliazzo, Russell; Kabanets, Valentine 4 2017 On the connection between interval size functions and path counting. Zbl 1401.68107 Bampas, Evangelos; Göbel, Andreas-Nikolas; Pagourtzis, Aris; Tentes, Aris 3 2017 Low-degree test with polynomially small error. Zbl 1378.68052 Moshkovitz, Dana 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 Dual VP classes. Zbl 1378.68046 Allender, Eric; Gál, Anna; Mertz, Ian 1 2017 A dichotomy for real weighted Holant problems. Zbl 1336.68099 Huang, Sangxia; Lu, Pinyan 24 2016 Cryptographic hardness of random local functions. Survey. Zbl 1360.94293 Applebaum, Benny 14 2016 Factors of low individual degree polynomials. Zbl 1345.68292 Oliveira, Rafael 10 2016 Combinatorial PCPs with short proofs. Zbl 1336.68090 Meir, Or 7 2016 Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Zbl 1345.68126 Applebaum, Benny; Artemenko, Sergei; Shaltiel, Ronen; Yang, Guang 7 2016 Collapse of the hierarchy of constant-depth exact quantum circuits. Zbl 1353.68097 Takahashi, Yasuhiro; Tani, Seiichiro 6 2016 Unprovable security of perfect NIZK and non-interactive non-malleable commitments. Zbl 1369.94562 Pass, Rafael 5 2016 On the power of algebraic branching programs of width two. Zbl 1348.68061 Allender, Eric; Wang, Fengming 5 2016 Lower bounds for depth-three arithmetic circuits with small bottom fanin. Zbl 1345.68161 Kayal, Neeraj; Saha, Chandan 4 2016 The complexity of intersecting finite automata having few final states. Zbl 1353.68109 Blondin, Michael; Krebs, Andreas; McKenzie, Pierre 3 2016 Affine extractors over large fields with exponential error. Zbl 1419.11132 Bourgain, Jean; Dvir, Zeev; Leeman, Ethan 3 2016 The complexity of estimating min-entropy. Zbl 1336.68109 Watson, Thomas 3 2016 Subexponential size hitting sets for bounded depth multilinear formulas. Zbl 1344.68090 Oliveira, Rafael; Shpilka, Amir; Volk, Ben Lee 3 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 Quantum commitments from complexity assumptions. Zbl 1336.81030 Chailloux, André; Kerenidis, Iordanis; Rosgen, Bill 2 2016 Testing list \(H\)-homomorphisms. Zbl 1353.68139 Yoshida, Yuichi 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 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 Mining circuit lower bound proofs for meta-algorithms. Zbl 1401.68116 Chen, Ruiwen; Kabanets, Valentine; Kolokolova, Antonina; Shaltiel, Ronen; Zuckerman, David 34 2015 Equivalence of polynomial identity testing and polynomial factorization. Zbl 1319.65035 Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir 18 2015 Read-once polynomial identity testing. Zbl 1329.68147 Shpilka, Amir; Volkovich, Ilya 15 2015 ...and 348 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 3,955 Authors 38 Goldreich, Oded 35 Cai, Jin-Yi 35 Wigderson, Avi 32 Pitassi, Toniann 31 Servedio, Rocco A. 30 Arvind, Vikraman 29 Allender, Eric W. 28 Ishai, Yuval 28 Williams, Richard Ryan 26 Schost, Éric 25 Impagliazzo, Russell 25 Mahajan, Meena 25 Santhanam, Rahul 25 Srinivasan, Srikanth 24 Applebaum, Benny 24 Chiesa, Alessandro 24 Fortnow, Lance J. 22 Grigor’ev, Dmitriĭ Yur’evich 22 Limaye, Nutan 22 Lovett, Shachar 22 Saxena, Nitin 21 Ben-Sasson, Eli 21 Shpilka, Amir 21 Watson, Thomas 20 Kabanets, Valentine 20 O’Donnell, Ryan 19 Basu, Saugata 19 Filmus, Yuval 19 Kumar, Mrinal 18 Buss, Samuel R. 18 Chattopadhyay, Arkadev 18 Sherstov, Alexander A. 18 Sudan, Madhu 18 Viola, Emanuele 17 Dinur, Irit 17 Göös, Mika 17 Ikenmeyer, Christian 17 Meir, Or 17 Raghavendra Rao, B. V. 17 Raz, Ran 17 Shaltiel, Ronen 17 Yukna, Stasys P. 16 Gur, Tom 16 Koiran, Pascal 16 Rothblum, Ron D. 15 Atserias, Albert 15 Beyersdorff, Olaf 15 Hemaspaandra, Lane A. 15 Karpinski, Marek 15 Saha, Chandan 15 Shparlinski, Igor E. 14 Bürgisser, Peter 14 Dvir, Zeev 14 Gál, Anna 14 Galesi, Nicola 14 Guruswami, Venkatesan 14 Ivanyos, Gábor 14 Kayal, Neeraj 14 Khot, Subhash Ajit 14 Mukhopadhyay, Partha 14 Razborov, Aleksandr Aleksandrovich 14 Tal, Avishay 14 Tell, Roei 14 Vidick, Thomas 14 Zuckerman, David 13 Ambainis, Andris 13 Buhrman, Harry 13 Chen, Lijie 13 Feige, Uriel 13 Glaßer, Christian 13 Hirahara, Shuichi 13 Kothari, Pravesh K. 13 Lauria, Massimo 13 Lin, Huijia 13 Makam, Visu 13 Okhotin, Alexander 13 Oliveira, Igor Carboni 13 Vadhan, Salil P. 13 Volk, Ben Lee 12 Beimel, Amos 12 Braverman, Mark 12 Galanis, Andreas 12 Itsykson, Dmitry M. 12 Kushilevitz, Eyal 12 McKenzie, Pierre 12 Pudlák, Pavel 12 Qiao, Youming 12 Sahai, Amit 12 Saptharishi, Ramprasad 12 Saraf, Shubhangi 12 Shinkar, Igor 12 Thaler, Justin 12 Tzameret, Iddo 12 von zur Gathen, Joachim 11 Aaronson, Scott 11 Dal Lago, Ugo 11 de Wolf, Ronald Michiel 11 Fu, Zhiguo 11 Goldberg, Leslie Ann 11 Hatami, Pooya ...and 3,855 more Authors all top 5 Cited in 310 Journals 266 Theoretical Computer Science 203 Computational Complexity 133 SIAM Journal on Computing 132 Journal of Computer and System Sciences 99 Information and Computation 83 Theory of Computing Systems 80 Information Processing Letters 76 Algorithmica 52 Journal of Symbolic Computation 41 Discrete Applied Mathematics 36 Theory of Computing 34 Journal of Cryptology 32 Journal of Complexity 29 Annals of Pure and Applied Logic 29 Random Structures & Algorithms 27 Mathematics of Computation 26 Discrete Mathematics 25 Journal of Algebra 25 Designs, Codes and Cryptography 23 Linear Algebra and its Applications 22 Discrete & Computational Geometry 22 SIAM Journal on Discrete Mathematics 21 Mathematical Programming. Series A. Series B 20 Foundations of Computational Mathematics 18 International Journal of Foundations of Computer Science 18 Journal of Combinatorial Optimization 18 Journal of the ACM 16 Combinatorica 16 Combinatorics, Probability and Computing 16 The Electronic Journal of Combinatorics 16 ACM Transactions on Computation Theory 15 Quantum Information Processing 15 Logical Methods in Computer Science 14 Communications in Mathematical Physics 14 Applicable Algebra in Engineering, Communication and Computing 13 Journal of Pure and Applied Algebra 12 Advances in Mathematics 12 The Journal of Symbolic Logic 12 Archive for Mathematical Logic 10 Artificial Intelligence 10 ACM Transactions on Computational Logic 9 Israel Journal of Mathematics 9 Transactions of the American Mathematical Society 9 Mathematical Structures in Computer Science 9 Discrete Analysis 8 International Journal of Algebra and Computation 8 SIAM Journal on Optimization 8 Journal of Mathematical Sciences (New York) 8 The Bulletin of Symbolic Logic 8 Annals of Mathematics. Second Series 8 SIAM Journal on Applied Algebra and Geometry 8 TheoretiCS 7 Applied Mathematics and Computation 7 Chicago Journal of Theoretical Computer Science 7 Journal of High Energy Physics 7 Discrete Optimization 7 Forum of Mathematics, Sigma 6 Journal of Mathematical Physics 6 Physica A 6 The Annals of Probability 6 Probability Theory and Related Fields 6 Journal of the American Mathematical Society 6 Bulletin of the American Mathematical Society. New Series 6 Journal of Algebraic Combinatorics 6 RAIRO. Theoretical Informatics and Applications 6 Comptes Rendus. Mathématique. Académie des Sciences, Paris 6 Oberwolfach Reports 5 Information Sciences 5 Journal of Functional Analysis 5 Journal of Graph Theory 5 Journal of Number Theory 5 Mathematics and Computers in Simulation 5 Mathematics of Operations Research 5 European Journal of Combinatorics 5 Advances in Applied Mathematics 5 Graphs and Combinatorics 5 SIAM Journal on Matrix Analysis and Applications 5 Neural Computation 5 European Journal of Operational Research 5 Finite Fields and their Applications 5 Journal of the European Mathematical Society (JEMS) 5 Lobachevskii Journal of Mathematics 5 Journal of Mathematical Cryptology 5 Journal of Physics A: Mathematical and Theoretical 4 Computers & Mathematics with Applications 4 Linear and Multilinear Algebra 4 Computing 4 Journal of Combinatorial Theory. Series A 4 Proceedings of the American Mathematical Society 4 Operations Research Letters 4 The Journal of Fourier Analysis and Applications 4 LMS Journal of Computation and Mathematics 4 Journal of Statistical Mechanics: Theory and Experiment 4 International Journal of Number Theory 4 Advances in Mathematics of Communications 4 Algebra & Number Theory 4 Algorithms 4 Computability 4 Algebraic Combinatorics 3 Communications in Algebra ...and 210 more Journals all top 5 Cited in 53 Fields 2,709 Computer science (68-XX) 669 Information and communication theory, circuits (94-XX) 528 Combinatorics (05-XX) 377 Mathematical logic and foundations (03-XX) 270 Operations research, mathematical programming (90-XX) 246 Number theory (11-XX) 213 Quantum theory (81-XX) 163 Algebraic geometry (14-XX) 152 Linear and multilinear algebra; matrix theory (15-XX) 113 Probability theory and stochastic processes (60-XX) 109 Group theory and generalizations (20-XX) 103 Numerical analysis (65-XX) 95 Order, lattices, ordered algebraic structures (06-XX) 92 Commutative algebra (13-XX) 77 Field theory and polynomials (12-XX) 73 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 54 Associative rings and algebras (16-XX) 45 Convex and discrete geometry (52-XX) 39 Statistical mechanics, structure of matter (82-XX) 32 Statistics (62-XX) 26 Functional analysis (46-XX) 13 Nonassociative rings and algebras (17-XX) 13 Abstract harmonic analysis (43-XX) 12 Real functions (26-XX) 12 Differential geometry (53-XX) 12 Biology and other natural sciences (92-XX) 11 General and overarching topics; collections (00-XX) 11 Dynamical systems and ergodic theory (37-XX) 10 Approximations and expansions (41-XX) 10 Operator theory (47-XX) 10 Systems theory; control (93-XX) 9 History and biography (01-XX) 9 Ordinary differential equations (34-XX) 8 Category theory; homological algebra (18-XX) 8 Functions of a complex variable (30-XX) 8 Harmonic analysis on Euclidean spaces (42-XX) 8 Geometry (51-XX) 7 General algebraic systems (08-XX) 7 Measure and integration (28-XX) 7 Partial differential equations (35-XX) 6 Calculus of variations and optimal control; optimization (49-XX) 6 Algebraic topology (55-XX) 6 Manifolds and cell complexes (57-XX) 5 Difference and functional equations (39-XX) 5 Relativity and gravitational theory (83-XX) 4 Topological groups, Lie groups (22-XX) 4 Potential theory (31-XX) 4 Mechanics of particles and systems (70-XX) 2 \(K\)-theory (19-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) Citations by Year