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