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