Theory of Computing Short Title: Theory Comput. Publisher: University of Chicago, Department of Computer Science, Chicago, IL ISSN: 1557-2862/e Online: http://theoryofcomputing.org/articles/main/index.html Comments: Journal; Indexed cover-to-cover; Published electronic only as of Vol. 1 (2005). This journal is available open access. Documents Indexed: 317 Publications (since 2005) References Indexed: 201 Publications with 5,706 References. all top 5 Latest Issues 19 (2023) 18 (2022) 17 (2021) 16 (2020) 15 (2019) 14 (2018) 13 (2017) 12 (2016) 11 (2015) 10 (2014) 9 (2013) 8 (2012) 7 (2011) 6 (2010) 5 (2009) 4 (2008) 3 (2007) 2 (2006) 1 (2005) all top 5 Authors 10 Lovett, Shachar 9 Aaronson, Scott 8 Dvir, Zeev 8 Wigderson, Avi 7 Servedio, Rocco A. 6 Bansal, Nikhil 6 Håstad, Johan Torkel 6 O’Donnell, Ryan 6 Srinivasan, Srikanth 6 Viola, Emanuele 5 Chekuri, Chandra S. 5 Guruswami, Venkatesan 5 Khot, Subhash Ajit 5 Mossel, Elchanan 5 Regev, Oded 5 Sherstov, Alexander A. 5 Shpilka, Amir 5 Vadhan, Salil P. 4 Ambainis, Andris 4 Austrin, Per 4 Feige, Uriel 4 Harsha, Prahladh 4 Hrubeš, Pavel 4 Kopparty, Swastik 4 Krauthgamer, Robert 4 Ron-Zewi, Noga 4 Sudan, Madhu 4 Williams, Richard Ryan 3 Alon, Noga 3 Blum, Avrim L. 3 Briët, Jop 3 Bun, Mark 3 Chakrabarty, Deeparnab 3 Dadush, Daniel 3 De, Anindya K. 3 Göös, Mika 3 Haviv, Ishay 3 Huang, Sangxia 3 Kumar, Mrinal 3 Kuperberg, Gregory John 3 Makarychev, Yury S. 3 Manokaran, Rajsekar 3 Pitassi, Toniann 3 Raskhodnikova, Sofya 3 Raz, Ran 3 Saks, Michael E. 3 Špalek, Robert 3 Srinivasan, Aravind 3 Svensson, Ola 3 Ta-Shma, Amnon 3 Tan, Liyang 3 Thaler, Justin 3 Trevisan, Luca 3 Wan, Andrew 3 Yehudayoff, Amir 3 Zhang, Shengyu 2 Ajtai, Miklós 2 Allender, Eric W. 2 Arora, Sanjeev 2 Balcan, Maria-Florina 2 Beigi, Salman 2 Ben-Aroya, Avraham 2 Ben-Sasson, Eli 2 Bhangale, Amey 2 Blais, Eric 2 Braverman, Mark 2 Canonne, Clement Louis 2 Childs, Andrew M. 2 Chlamtac, Eden 2 Chuzhoy, Julia 2 Dasgupta, Anirban 2 Diakonikolas, Ilias 2 Drucker, Andrew 2 Fefferman, Bill 2 Filmus, Yuval 2 Fischer, Eldar 2 Forbes, Michael A. 2 Fortnow, Lance J. 2 Garg, Shashwat 2 Gavinsky, Dmitry 2 Goyal, Navin 2 Guo, Siyao 2 Gupta, Anupam 2 Haramaty, Elad 2 Hatami, Hamed 2 Holenstein, Thomas 2 Hosseini, Kaave 2 Jain, Rahul 2 Kamath, Pritish 2 Khanna, Sanjeev 2 Klivans, Adam R. 2 Kothari, Robin 2 Kumar, Ravi K. 2 Landsberg, Joseph Montague 2 Lee, Chin Ho 2 Lee, Euiwoong 2 Lee, Homin K. 2 Limaye, Nutan 2 Magen, Avner 2 Meka, Raghu ...and 391 more Authors all top 5 Fields 296 Computer science (68-XX) 46 Information and communication theory, circuits (94-XX) 37 Combinatorics (05-XX) 33 Quantum theory (81-XX) 32 Operations research, mathematical programming (90-XX) 16 Number theory (11-XX) 16 Probability theory and stochastic processes (60-XX) 15 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 14 Mathematical logic and foundations (03-XX) 12 General and overarching topics; collections (00-XX) 11 Linear and multilinear algebra; matrix theory (15-XX) 10 Convex and discrete geometry (52-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 6 Numerical analysis (65-XX) 4 Field theory and polynomials (12-XX) 4 Group theory and generalizations (20-XX) 4 Harmonic analysis on Euclidean spaces (42-XX) 4 Statistics (62-XX) 2 History and biography (01-XX) 2 Algebraic geometry (14-XX) 1 Commutative algebra (13-XX) 1 Associative rings and algebras (16-XX) 1 Real functions (26-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Approximations and expansions (41-XX) 1 Functional analysis (46-XX) 1 Differential geometry (53-XX) 1 Manifolds and cell complexes (57-XX) 1 Optics, electromagnetic theory (78-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 236 Publications have been cited 2,353 times in 2,027 Documents Cited by ▼ Year ▼ Maximizing the spread of influence through a social network. Zbl 1337.91069Kempe, David; Kleinberg, Jon; Tardos, Éva 349 2015 Linear degree extractors and the inapproximability of max clique and chromatic number. Zbl 1213.68322Zuckerman, David 182 2007 A quantum algorithm for the Hamiltonian NAND tree. Zbl 1213.68284Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam 120 2008 The multiplicative weights update method: a meta-algorithm and applications. Zbl 1283.68414Arora, Sanjeev; Hazan, Elad; Kale, Satyen 88 2012 Can you beat treewidth? Zbl 1213.68316Marx, Dániel 59 2010 Quantum search of spatial regions. Zbl 1213.68279Aaronson, Scott; Ambainis, Andris 38 2005 Approximate nearest neighbor: towards removing the curse of dimensionality. Zbl 1278.68344Har-Peled, Sariel; Indyk, Piotr; Motwani, Rajeev 36 2012 The computational complexity of linear optics. Zbl 1298.81046Aaronson, Scott; Arkhipov, Alex 35 2013 New lower bounds for the border rank of matrix multiplication. Zbl 1336.68102Landsberg, Joseph M.; Ottaviani, Giorgio 32 2015 Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Zbl 1213.68281Ambainis, Andris 31 2005 Inapproximability of vertex cover and independent set in bounded degree graphs. Zbl 1243.68183Austrin, Per; Khot, Subhash; Safra, Muli 31 2011 Separation of multilinear circuit and formula size. Zbl 1213.68301Raz, Ran 27 2006 The projection games conjecture and the NP-hardness of \(\ln n\)-approximating Set-Cover. Zbl 1335.68097Moshkovitz, Dana 26 2015 Proving integrality gaps without knowing the linear program. Zbl 1213.68306Arora, Sanjeev; Bollobás, Béla; Lovász, László; Tourlakis, Iannis 25 2006 An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Zbl 1213.68700Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce 25 2006 Near-optimal network design with selfish agents. Zbl 1213.68698Anshelevich, Elliot; Dasgupta, Anirban; Tardos, Éva; Wexler, Tom 23 2008 Rank bounds and integrality gaps for cutting planes procedures. Zbl 1213.68328Buresh-Oppenheim, Joshua; Galesi, Nicola; Hoory, Shlomo; Magen, Avner; Pitassi, Toniann 21 2006 Distance transforms of sampled functions. Zbl 1280.68266Felzenszwalb, Pedro F.; Huttenlocher, Daniel P. 20 2012 How hard is it to approximate the Jones polynomial? Zbl 1337.68109Kuperberg, Greg 20 2015 Locally checkable proofs in distributed computing. Zbl 1401.68085Göös, Mika; Suomela, Jukka 20 2016 Correlation clustering with a fixed number of clusters. Zbl 1213.68704Giotis, Ioannis; Guruswami, Venkatesan 19 2006 Approximation algorithms and online mechanisms for item pricing. Zbl 1213.68699Balcan, Maria-Florina; Blum, Avrim 19 2007 The submodular welfare problem with demand queries. Zbl 1213.68703Feige, Uriel; Vondrák, Jan 19 2010 Elusive functions and lower bounds for arithmetic circuits. Zbl 1213.68318Raz, Ran 18 2010 Near-optimal and explicit Bell inequality violations. Zbl 1298.81034Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald 17 2012 Limitations of quantum advice and one-way communication. Zbl 1213.68278Aaronson, Scott 16 2005 Matrix approximation and projective clustering via volume sampling. Zbl 1213.68702Deshpande, Amit; Rademacher, Luis; Vempala, Santosh; Wang, Grant 16 2006 Norms, XOR lemmas, and lower bounds for polynomials and protocols. Zbl 1213.68321Viola, Emanuele; Wigderson, Avi 16 2008 Anti-concentration for polynomials of independent random variables. Zbl 1392.68193Meka, Raghu; Nguyen, Oanh; Vu, Van 16 2016 The randomized communication complexity of set disjointness. Zbl 1213.68332Håstad, Johan; Wigderson, Avi 15 2007 Semidefinite programs for completely bounded norms. Zbl 1213.81047Watrous, John 15 2009 A separation of NP and conp in multiparty communication complexity. Zbl 1213.68293Gavinsky, Dmitry; Sherstov, Alexander A. 15 2010 The one-way communication complexity of Hamming distance. Zbl 1213.68334Jayram, T. S.; Kumar, Ravi; Sivakumar, D. 14 2008 Quantum expanders: motivation and construction. Zbl 1213.81052Ben-Aroya, Avraham; Schwartz, Oded; Ta-Shma, Amnon 14 2010 List-decoding multiplicity codes. Zbl 1397.94127Kopparty, Swastik 14 2015 The need for structure in quantum speedups. Zbl 1298.81045Aaronson, Scott; Ambainis, Andris 14 2014 Quantum lower bound for the collision problem with small range. Zbl 1213.68286Kutin, Samuel 13 2005 The communication complexity of gap Hamming distance. Zbl 1253.68158Sherstov, Alexander A. 13 2012 Matchgates revisited. Zbl 1342.68156Cai, Jin-Yi; Gorenstein, Aaron 13 2014 Computing the partition function for cliques in a graph. Zbl 1351.05212Barvinok, Alexander 13 2015 Quantum fan-out is powerful. Zbl 1213.68298Høyer, Peter; Špalek, Robert 12 2005 The power of unentanglement. Zbl 1213.68280Aaronson, Scott; Beigi, Salman; Drucker, Andrew; Fefferman, Bill; Shor, Peter 12 2009 Unconditional pseudorandom generators for low degree polynomials. Zbl 1213.68274Lovett, Shachar 12 2009 Parallel repetition: simplification and the no-signaling case. Zbl 1213.68297Holenstein, Thomas 12 2009 Regularity lemmas and combinatorial algorithms. Zbl 1253.68162Bansal, Nikhil; Williams, Ryan 12 2012 Revenue submodularity. Zbl 1246.91054Dughmi, Shaddin; Roughgarden, Tim; Sundararajan, Mukund 12 2012 On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity. Zbl 1378.68053Murray, Cody D.; Williams, R. Ryan 12 2017 Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states. Zbl 1362.68087McKague, Matthew 12 2016 Grothendieck inequalities for semidefinite programs with rank constraint. Zbl 1297.68261Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank 12 2014 Query efficient PCPs with perfect completeness. Zbl 1213.68331Håstad, Johan; Khot, Subhash 11 2005 An exponential separation between regular and general resolution. Zbl 1213.68303Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair 11 2007 Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Zbl 1213.68697Wigderson, Avi; Xiao, David 11 2008 All quantum adversary methods are equivalent. Zbl 1213.68289Špalek, Robert; Szegedy, Mario 10 2006 Tensor products of weakly smooth codes are robust. Zbl 1213.68252Ben-Sasson, Eli; Viderman, Michael 10 2009 Monotone expanders: constructions and applications. Zbl 1213.68440Dvir, Zeev; Wigderson, Avi 10 2010 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152Haviv, Ishay; Regev, Oded 10 2012 Pseudorandomness for width-2 branching programs. Zbl 1300.68037Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir 10 2013 Quantum versus classical proofs and advice. Zbl 1213.68290Aaronson, Scott; Kuperberg, Greg 9 2007 Discrete-query quantum algorithm for NAND trees. Zbl 1213.68283Childs, Andrew M.; Cleve, Richard; Jordan, Stephen P.; Yonge-Mallo, David 9 2009 All pairs bottleneck paths and max-min matrix products in truly subcubic time. Zbl 1213.68338Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael 9 2009 Tight bounds on the average sensitivity of k-CNF. Zbl 1213.68416Amano, Kazuyuki 9 2011 Inapproximability of the shortest vector problem: toward a deterministic reduction. Zbl 1282.68127Micciancio, Daniele 9 2012 An optimal lower bound for monotonicity testing over hypergrids. Zbl 1319.68098Chakrabarty, Deeparnab; Seshadhri, C. 9 2014 Quantum-walk speedup of backtracking algorithms. Zbl 1417.68046Montanaro, Ashley 9 2018 Solving packing integer programs via randomized rounding with alterations. Zbl 1297.68259Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind 9 2012 Inapproximability of NP-complete variants of Nash equilibrium. Zbl 1366.68071Austrin, Per; Braverman, Mark; Chlamtáč, Eden 9 2013 Non-commutative arithmetic circuits with division. Zbl 1403.94130Hrubeš, Pavel; Wigderson, Avi 9 2015 Span-program-based quantum algorithm for evaluating formulas. Zbl 1279.68097Reichardt, Ben; Špalek, Robert 8 2012 How to verify a quantum computation. Zbl 1395.68142Broadbent, Anne 8 2018 Approximating the AND-OR tree. Zbl 1328.68078Sherstov, Alexander A. 8 2013 On beating the hybrid argument. Zbl 1298.81047Fefferman, Bill; Shaltiel, Ronen; Umans, Christopher; Viola, Emanuele 8 2013 A non-linear time lower bound for Boolean branching programs. Zbl 1213.68302Ajtai, Miklós 7 2005 Iterative construction of Cayley expander graphs. Zbl 1213.05127Rozenman, Eyal; Shalev, Aner; Wigderson, Avi 7 2006 Approximation algorithms for unique games. Zbl 1213.68320Trevisan, Luca 7 2008 On circuit lower bounds from derandomization. Zbl 1247.68091Aaronson, Scott; van Melkebeek, Dieter 7 2011 Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1253.68068Bansal, Nikhil; Chan, Ho-Leung; Katz, Dmitriy; Pruhs, Kirk 7 2012 An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design. Zbl 1253.68167Chuzhoy, Julia; Khanna, Sanjeev 7 2012 Width-parametrized SAT: time-space tradeoffs. Zbl 1319.68094Allender, Eric; Chen, Shiteng; Lou, Tiancheng; Papakonstantinou, Periklis A.; Tang, Bangsheng 7 2014 Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122Briët, Jop; Regev, Oded; Saket, Rishi 7 2017 On the hardness of learning with errors with binary secrets. Zbl 1412.68072Micciancio, Daniele 7 2018 A tradeoff between length and width in resolution. Zbl 1355.03047Thapen, Neil 7 2016 Making polynomials robust to noise. Zbl 1366.68063Sherstov, Alexander A. 7 2013 Bounding the sensitivity of polynomial threshold functions. Zbl 1366.68096Harsha, Prahladh; Klivans, Adam; Meka, Raghu 7 2014 Conditional random fields, planted constraint satisfaction, and entropy concentration. Zbl 1351.68190Abbe, Emmanuel; Montanari, Andrea 7 2015 Learning restricted models of arithmetic circuits. Zbl 1213.68341Klivans, Adam; Shpilka, Amir 6 2006 Testing linear-invariant non-linear properties. Zbl 1246.68259Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 6 2011 Arithmetic complexity in ring extensions. Zbl 1234.03027Hrubeš, Pavel; Yehudayoff, Amir 6 2011 Inverse conjecture for the Gowers norm is false. Zbl 1282.11009Lovett, Shachar; Meshulam, Roy; Samorodnitsky, Alex 6 2011 Time-space efficient simulations of quantum computations. Zbl 1253.68136Van Melkebeek, Dieter; Watson, Thomas 6 2012 SDP gaps from pairwise independence. Zbl 1253.68141Benabbas, Siavosh; Georgiou, Konstantinos; Magen, Avner; Tulsiani, Madhur 6 2012 Potential-function proofs for gradient methods. Zbl 1482.90145Bansal, Nikhil; Gupta, Anupam 6 2019 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 6 2018 Communication complexity of set-disjointness for all probabilities. Zbl 1365.68259Göös, Mika; Watson, Thomas 6 2016 The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122Faben, John; Jerrum, Mark 6 2015 Lower bounds for non-commutative skew circuits. Zbl 1393.68063Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth 6 2016 The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Zbl 1366.68073Gottesman, Daniel; Irani, Sandy 6 2013 Towards an optimal separation of space and length in resolution. Zbl 1366.68098Nordström, Jakob; Håstad, Johan 6 2013 Circumventing \(d\)-to-\(1\) for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Zbl 1366.68084Wenner, Cenny 6 2013 Hardness of vertex deletion and project scheduling. Zbl 1366.68083Svensson, Ola 6 2013 A regularity lemma and low-weight approximators for low-degree polynomial threshold functions. Zbl 1366.68089Diakonikolas, Ilias; Servedio, Rocco A.; Tan, Li-Yang; Wan, Andrew 6 2014 Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions. Zbl 07528585Chen, Zongchen; Vempala, Santosh S. 4 2022 Max-min greedy matching. Zbl 07528582Eden, Alon; Feige, Uriel; Feldman, Michal 1 2022 Barriers for fast matrix multiplication from irreversibility. Zbl 07413497Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen 3 2021 Limits on the universal method for matrix multiplication. Zbl 07413496Alman, Josh 2 2021 Deterministic approximation of random walks in small space. Zbl 07413499Murtagh, Jack; Reingold, Omer; Sidford, Aaron; Vadhan, Salil 2 2021 The large-error approximate degree of \(\mathrm{AC}^0\). Zbl 07413502Bun, Mark; Thaler, Justin 1 2021 Sherali-Adams strikes back. Zbl 07413504O’Donnell, Ryan; Schramm, Tselil 1 2021 The polynomial method strikes back: tight quantum query bounds via dual polynomials. Zbl 1462.68060Bun, Mark; Kothari, Robin; Thaler, Justin 3 2020 Relaxed locally correctable codes. Zbl 1477.68110Gur, Tom; Ramnarayan, Govind; Rothblum, Ron 2 2020 Fourier and circulant matrices are not rigid. Zbl 1477.68117Dvir, Zeev; Liu, Allen 2 2020 On the hardness of approximate and exact (bichromatic) maximum inner product. Zbl 1462.68067Chen, Lijie 2 2020 On the hardness of approximating the \(k\)-Way Hypergraph Cut problem. Zbl 1462.68066Chekuri, Chandra; Li, Shi 2 2020 Concentration for limited independence via inequalities for the elementary symmetric polynomials. Zbl 1483.65014Gopalan, Parikshit; Yehudayoff, Amir 1 2020 Distributed corruption detection in networks. Zbl 1454.05115Alon, Noga; Mossel, Elchanan; Pemantle, Robin 1 2020 On the classical hardness of spoofing linear cross-entropy benchmarking. Zbl 1454.81047Aaronson, Scott; Gunn, Sam 1 2020 Potential-function proofs for gradient methods. Zbl 1482.90145Bansal, Nikhil; Gupta, Anupam 6 2019 Matrix rigidity and the Croot-Lev-Pach lemma. Zbl 1477.68116Dvir, Zeev; Edelman, Benjamin L. 5 2019 Closure results for polynomial factorization. Zbl 1477.68106Chou, Chi-Ning; Kumar, Mrinal; Solomon, Noam 5 2019 Algebraic dependencies and \(\mathsf{PSPACE}\) algorithms in approximative complexity over any field. Zbl 1456.68058Guo, Zeyu; Saxena, Nitin; Sinhababu, Amit 2 2019 The threshold for subgroup profiles to agree is logarithmic. Zbl 1494.68100Wilson, James B. 2 2019 Subsets of Cayley graphs that induce many edges. Zbl 1496.05073Gowers, Timothy; Janzer, Oliver 2 2019 Randomized polynomial-time identity testing for noncommutative circuits. Zbl 1477.68531Arvind, Vikraman; Joglekar, Pushkar S.; Mukhopadhyay, Partha; Raja, S. 2 2019 Outlaw distributions and locally decodable codes. Zbl 1477.94080Briët, Jop; Dvir, Zeev; Gopi, Sivakanth 2 2019 Towards a constructive version of Banaszczyk’s vector balancing theorem. Zbl 1494.52002Dadush, Daniel; Garg, Shashwat; Lovett, Shachar; Nikolov, Aleksandar 1 2019 Lower bounds for data structures with space close to maximum imply circuit lower bounds. Zbl 1494.68093Viola, Emanuele 1 2019 The Gram-Schmidt walk: a cure for the Banaszczyk blues. Zbl 1494.68267Bansal, Nikhil; Dadush, Daniel; Garg, Shashwat; Lovett, Shachar 1 2019 Explicit polynomial sequences with maximal spaces of partial derivatives and a question of K. Mulmuley. Zbl 1477.68113Gesmundo, Fulvio; Landsberg, Joseph M. 1 2019 Quantum-walk speedup of backtracking algorithms. Zbl 1417.68046Montanaro, Ashley 9 2018 How to verify a quantum computation. Zbl 1395.68142Broadbent, Anne 8 2018 On the hardness of learning with errors with binary secrets. Zbl 1412.68072Micciancio, Daniele 7 2018 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 6 2018 Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression. Zbl 1412.68071Kopparty, Swastik; Srinivasan, Srikanth 4 2018 Trading information complexity for error. Zbl 1394.68148Dagan, Yuval; Filmus, Yuval; Hatami, Hamed; Li, Yaqiao 3 2018 Randomized query complexity of sabotaged and composed functions. Zbl 1398.68186Ben-David, Shalev; Kothari, Robin 3 2018 On multiparty communication with large versus unbounded error. Zbl 1412.68061Sherstov, Alexander A. 3 2018 A deterministic PTAS for the commutative rank of matrix spaces. Zbl 1395.68333Bläser, Markus; Jindal, Gorav; Pandey, Anurag 2 2018 Small extended formulation for knapsack cover inequalities from monotone circuits. Zbl 1426.90211Bazzi, Abbas; Fiorini, Samuel; Huang, Sangxia; Svensson, Ola 2 2018 On the size of homogeneous and of depth-four formulas with low individual degree. Zbl 1410.68125Kayal, Neeraj; Saha, Chandan; Tavenas, Sébastien 2 2018 New algorithms and lower bounds for circuits with linear threshold gates. Zbl 1410.68127Williams, R. Ryan 2 2018 Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Zbl 1412.68081Forbes, Michael A.; Shpilka, Amir; Volk, Ben Lee 2 2018 Simplified separation of information and communication. Zbl 1412.68060Rao, Anup; Sinha, Makrand 2 2018 Linear-time algorithm for quantum 2SAT. Zbl 1395.68132Arad, Itai; Santha, Miklos; Sundaram, Aarthi; Zhang, Shengyu 1 2018 From weak to strong linear programming gaps for all constraint satisfaction problems. Zbl 1394.68178Ghosh, Mrinalkanti; Tulsiani, Madhur 1 2018 The complexity of computing the optimal composition of differential privacy. Zbl 1395.94305Murtagh, Jack; Vadhan, Salil 1 2018 Separation of unbounded-error models in multi-party communication complexity. Zbl 1414.68027Chattopadhyay, Arkadev; Mande, Nikhil S. 1 2018 On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity. Zbl 1378.68053Murray, Cody D.; Williams, R. Ryan 12 2017 Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122Briët, Jop; Regev, Oded; Saket, Rishi 7 2017 Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Zbl 1378.68080Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin 4 2017 Superquadratic lower bound for 3-query locally correctable codes over the reals. Zbl 1375.94176Dvir, Zeev; Saraf, Shubhangi; Wigderson, Avi 4 2017 Pseudorandomness and Fourier-growth bounds for width-3 branching programs. Zbl 1377.65003Steinke, Thomas; Vadhan, Salil; Wan, Andrew 3 2017 Nash equilibria in perturbation-stable games. Zbl 1380.91011Balcan, Maria-Florina; Braverman, Mark 2 2017 The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems. Zbl 1387.68127Shepherd, F. Bruce; Vetta, Adrian R. 2 2017 Some limitations of the sum of small-bias distributions. Zbl 1387.68125Lee, Chin Ho; Viola, Emanuele 2 2017 The shifted partial derivative complexity of elementary symmetric polynomials. Zbl 1379.68149Fournier, Hervé; Limaye, Nutan; Mahajan, Meena; Srinivasan, Srikanth 1 2017 The minimum bisection in the planted bisection model. Zbl 1379.05099Coja-Oghlan, Amin; Cooley, Oliver; Kang, Mihyun; Skubch, Kathrin 1 2017 A communication game related to the sensitivity conjecture. Zbl 1379.68151Gilmer, Justin; Koucký, Michal; Saks, Michael 1 2017 Arithmetic circuits with locally low algebraic rank. Zbl 1378.68051Kumar, Mrinal; Saraf, Shubhangi 1 2017 A randomized online quantile summary in \(O((1/\varepsilon) \log(1/\varepsilon))\) words. Zbl 1382.68325Felber, David; Ostrovsky, Rafail 1 2017 Decoding Reed-Muller codes over product sets. Zbl 1420.94114Kim, John Y.; Kopparty, Swastik 1 2017 Monotone projection lower bounds from extended formulation lower bounds. Zbl 1383.68036Grochow, Joshua A. 1 2017 Locally checkable proofs in distributed computing. Zbl 1401.68085Göös, Mika; Suomela, Jukka 20 2016 Anti-concentration for polynomials of independent random variables. Zbl 1392.68193Meka, Raghu; Nguyen, Oanh; Vu, Van 16 2016 Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states. Zbl 1362.68087McKague, Matthew 12 2016 A tradeoff between length and width in resolution. Zbl 1355.03047Thapen, Neil 7 2016 Communication complexity of set-disjointness for all probabilities. Zbl 1365.68259Göös, Mika; Watson, Thomas 6 2016 Lower bounds for non-commutative skew circuits. Zbl 1393.68063Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth 6 2016 Lattice sparsification and the approximate closest vector problem. Zbl 1362.68291Dadush, Daniel; Kun, Gábor 5 2016 Private learning and sanitization: pure vs. approximate differential privacy. Zbl 1362.68096Beimel, Amos; Nissim, Kobbi; Stemmer, Uri 3 2016 Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11080Kopparty, Swastik; Kumar, Mrinal; Saks, Michael 3 2016 Simple proof of hardness of feedback vertex set. Zbl 1343.68095Guruswami, Venkatesan; Lee, Euiwoong 3 2016 Dual polynomials for collision and element distinctness. Zbl 1393.68055Bun, Mark; Thaler, Justin 3 2016 Lowest-degree \(k\)-spanner: approximation and hardness. Zbl 1393.68187Chlamtáč, Eden; Dinitz, Michael 3 2016 Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. Zbl 1353.81035Lin, Cedric Yen-Yu; Lin, Han-Hsuan 3 2016 Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion. Zbl 1393.68190Louis, Anand; Makarychev, Yury 2 2016 Robust lower bounds for communication and stream computation. Zbl 1392.68191Chakrabarti, Amit; Cormode, Graham; Mcgregor, Andrew 2 2016 Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 1 2016 Majority is stablest: discrete and SoS. Zbl 1362.68090De, Anindya; Mossel, Elchanan; Neeman, Joe 1 2016 Minimizing maximum flow-time on related machines. Zbl 1391.90239Bansal, Nikhil; Cloostermans, Bouke 1 2016 Maximizing the spread of influence through a social network. Zbl 1337.91069Kempe, David; Kleinberg, Jon; Tardos, Éva 349 2015 New lower bounds for the border rank of matrix multiplication. Zbl 1336.68102Landsberg, Joseph M.; Ottaviani, Giorgio 32 2015 The projection games conjecture and the NP-hardness of \(\ln n\)-approximating Set-Cover. Zbl 1335.68097Moshkovitz, Dana 26 2015 How hard is it to approximate the Jones polynomial? Zbl 1337.68109Kuperberg, Greg 20 2015 List-decoding multiplicity codes. Zbl 1397.94127Kopparty, Swastik 14 2015 Computing the partition function for cliques in a graph. Zbl 1351.05212Barvinok, Alexander 13 2015 Non-commutative arithmetic circuits with division. Zbl 1403.94130Hrubeš, Pavel; Wigderson, Avi 9 2015 Conditional random fields, planted constraint satisfaction, and entropy concentration. Zbl 1351.68190Abbe, Emmanuel; Montanari, Andrea 7 2015 The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122Faben, John; Jerrum, Mark 6 2015 On some extensions of the FKN theorem. Zbl 1352.60029Jendrej, Jacek; Oleszkiewicz, Krzysztof; Wojtaszczyk, Jakub O. 5 2015 Adapt or die: polynomial lower bounds for non-adaptive dynamic data structures. Zbl 1351.68084Brody, Joshua; Larsen, Kasper Green 4 2015 On the NP-hardness of approximating ordering-constraint satisfaction problems. Zbl 1335.68094Austrin, Per; Manokaran, Rajsekar; Wenner, Cenny 3 2015 Quantum interactive proofs and the complexity of separability testing. Zbl 1336.68082Gutoski, Gus; Hayden, Patrick; Milner, Kevin; Wilde, Mark M. 3 2015 Quantum algorithm for monotonicity testing on the hypercube. Zbl 1351.68105Belovs, Aleksandrs; Blais, Eric 3 2015 Absolutely sound testing of lifted codes. Zbl 1337.68289Haramaty, Elad; Ron-Zewi, Noga; Sudan, Madhu 2 2015 A new regularity lemma and faster approximation algorithms for low threshold rank graphs. Zbl 1337.68295Oveis Gharan, Shayan; Trevisan, Luca 2 2015 The complexity of deciding statistical properties of samplable distributions. Zbl 1336.68108Watson, Thomas 1 2015 The need for structure in quantum speedups. Zbl 1298.81045Aaronson, Scott; Ambainis, Andris 14 2014 Matchgates revisited. Zbl 1342.68156Cai, Jin-Yi; Gorenstein, Aaron 13 2014 Grothendieck inequalities for semidefinite programs with rank constraint. Zbl 1297.68261Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank 12 2014 An optimal lower bound for monotonicity testing over hypergrids. Zbl 1319.68098Chakrabarty, Deeparnab; Seshadhri, C. 9 2014 Width-parametrized SAT: time-space tradeoffs. Zbl 1319.68094Allender, Eric; Chen, Shiteng; Lou, Tiancheng; Papakonstantinou, Periklis A.; Tang, Bangsheng 7 2014 ...and 136 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 3,446 Authors 18 Wu, Weili 16 Guruswami, Venkatesan 15 Srinivasan, Srikanth 13 Hoefer, Martin 12 Bonnet, Edouard 11 Palazuelos, Carlos 11 Thaler, Justin 10 Ambainis, Andris 10 D’Angelo, Gianlorenzo 10 Gargano, Luisa 10 Khot, Subhash Ajit 10 Lampis, Michael 10 Le Gall, François 10 Limaye, Nutan 10 Marx, Dániel 10 Ron-Zewi, Noga 10 Sherstov, Alexander A. 9 Goldberg, Leslie Ann 9 Grigorescu, Elena 9 Yoshida, Yuichi 8 Aaronson, Scott 8 Allender, Eric W. 8 Bun, Mark 8 Cai, Jin-Yi 8 Chekuri, Chandra S. 8 Cordasco, Gennaro 8 Feuilloley, Laurent 8 Fraigniaud, Pierre 8 Kumar, Mrinal 8 Landsberg, Joseph Montague 8 Mahajan, Meena 8 Manurangsi, Pasin 8 Massarenti, Alex 8 Miyano, Eiji 8 Naor, Assaf 8 Pitassi, Toniann 8 Pokutta, Sebastian 8 Rautenbach, Dieter 8 Rescigno, Adele Anna 8 Santha, Miklos 8 Shpilka, Amir 8 Sikora, Florian 8 Viola, Emanuele 7 Bazgan, Cristina 7 Briët, Jop 7 Chalermsook, Parinya 7 Chattopadhyay, Arkadev 7 Childs, Andrew M. 7 Chuzhoy, Julia 7 Dinur, Irit 7 Elbassioni, Khaled M. 7 Filmus, Yuval 7 Fu, Zhiguo 7 Halldórsson, Magnús Mar 7 Harsha, Prahladh 7 Huang, Chien-Chung 7 Niedermeier, Rolf 7 Ordyniak, Sebastian 7 Paschos, Vangelis Th. 7 Servedio, Rocco A. 7 Tani, Seiichiro 7 Tuza, Zsolt 7 Volk, Ben Lee 7 Wiese, Andreas 7 Wigderson, Avi 7 Wong, Thomas G. 7 Xu, Dachuan 7 Yang, Ruiqi 7 Yang, Wenguo 6 Alon, Noga 6 Barvinok, Alexander I. 6 Belovs, Aleksandrs 6 Borodin, Allan B. 6 Bousquet, Nicolas 6 Brandão, Fernando G. S. L. 6 Bulteau, Laurent 6 Caragiannis, Ioannis 6 Doron, Dean 6 Ene, Alina 6 Fiorini, Samuel 6 Froese, Vincent 6 Gao, Suixiang 6 Göös, Mika 6 Gur, Tom 6 Impagliazzo, Russell 6 Jansson, Jesper 6 Kwan, Matthew 6 Lovett, Shachar 6 Makino, Kazuhisa 6 Mathieu, Claire 6 Montealegre, Pedro 6 Nishimura, Harumichi 6 Nordström, Jakob 6 Qiao, Youming 6 Roughgarden, Tim 6 Saha, Chandan 6 Spirakis, Paul G. 6 Suchý, Ondřej 6 Thai, My T. 6 Tzameret, Iddo ...and 3,346 more Authors all top 5 Cited in 289 Journals 110 SIAM Journal on Computing 109 Theoretical Computer Science 100 Algorithmica 78 Quantum Information Processing 71 Computational Complexity 49 Discrete Applied Mathematics 46 Journal of Combinatorial Optimization 38 Theory of Computing Systems 30 SIAM Journal on Discrete Mathematics 28 Journal of Computer and System Sciences 27 Information Processing Letters 24 Mathematical Programming. Series A. Series B 22 Information and Computation 22 Discrete Optimization 21 Communications in Mathematical Physics 14 Journal of Mathematical Physics 14 Journal of the ACM 14 Theory of Computing 13 Journal of Machine Learning Research (JMLR) 12 Artificial Intelligence 11 Physica A 11 Combinatorica 10 Information Sciences 10 Random Structures & Algorithms 10 Distributed Computing 10 Data Mining and Knowledge Discovery 10 Journal of Physics A: Mathematical and Theoretical 9 Mathematics of Operations Research 9 Operations Research 9 Discrete & Computational Geometry 9 Annals of Operations Research 9 The Electronic Journal of Combinatorics 9 New Journal of Physics 8 Discrete Mathematics 8 Israel Journal of Mathematics 8 Journal of Statistical Physics 8 Journal of Global Optimization 8 Linear Algebra and its Applications 8 SIAM Journal on Optimization 8 Discrete Mathematics, Algorithms and Applications 8 Discrete Analysis 7 Journal of Cryptology 7 Games and Economic Behavior 7 Internet Mathematics 6 Automatica 6 Operations Research Letters 6 Computational Optimization and Applications 6 The Journal of Artificial Intelligence Research (JAIR) 6 Chicago Journal of Theoretical Computer Science 5 Physics Letters. A 5 European Journal of Combinatorics 5 Bulletin of the American Mathematical Society. New Series 5 INFORMS Journal on Computing 5 Journal of High Energy Physics 5 Annales Henri Poincaré 5 Foundations of Computational Mathematics 5 SIAM Journal on Applied Algebra and Geometry 4 International Journal of Theoretical Physics 4 The Annals of Probability 4 Computing 4 Journal of Combinatorial Theory. Series B 4 Journal of Pure and Applied Algebra 4 Graphs and Combinatorics 4 Probability Theory and Related Fields 4 Machine Learning 4 Geometric and Functional Analysis. GAFA 4 European Journal of Operational Research 4 Proceedings of the National Academy of Sciences of the United States of America 4 Journal of Graph Algorithms and Applications 4 International Journal of Quantum Information 4 Algorithms 4 ACM Transactions on Algorithms 4 Diskretnyĭ Analiz i Issledovanie Operatsiĭ 4 Computer Science Review 3 Computer Physics Communications 3 Journal of Computational Physics 3 Applied Mathematics and Computation 3 Bulletin of the London Mathematical Society 3 Journal of Computational and Applied Mathematics 3 Journal of Functional Analysis 3 Networks 3 Proceedings of the American Mathematical Society 3 SIAM Journal on Control and Optimization 3 Annals of Pure and Applied Logic 3 Journal of Symbolic Computation 3 Computers & Operations Research 3 SIAM Review 3 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques 3 Cybernetics and Systems Analysis 3 SIAM Journal on Scientific Computing 3 Combinatorics, Probability and Computing 3 Annals of Mathematics and Artificial Intelligence 3 Bernoulli 3 Geometry & Topology 3 Lobachevskii Journal of Mathematics 3 ACM Journal of Experimental Algorithmics 3 Journal of Discrete Algorithms 3 Foundations of Physics 3 Games 3 Journal of the Operations Research Society of China ...and 189 more Journals all top 5 Cited in 51 Fields 1,269 Computer science (68-XX) 433 Combinatorics (05-XX) 394 Operations research, mathematical programming (90-XX) 294 Quantum theory (81-XX) 286 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 167 Information and communication theory, circuits (94-XX) 78 Probability theory and stochastic processes (60-XX) 68 Linear and multilinear algebra; matrix theory (15-XX) 53 Mathematical logic and foundations (03-XX) 53 Statistics (62-XX) 51 Numerical analysis (65-XX) 44 Statistical mechanics, structure of matter (82-XX) 43 Number theory (11-XX) 34 Functional analysis (46-XX) 27 Algebraic geometry (14-XX) 26 Group theory and generalizations (20-XX) 26 Convex and discrete geometry (52-XX) 26 Biology and other natural sciences (92-XX) 25 Order, lattices, ordered algebraic structures (06-XX) 17 Operator theory (47-XX) 12 Commutative algebra (13-XX) 12 Harmonic analysis on Euclidean spaces (42-XX) 12 Manifolds and cell complexes (57-XX) 10 Field theory and polynomials (12-XX) 9 Calculus of variations and optimal control; optimization (49-XX) 7 Geometry (51-XX) 7 Systems theory; control (93-XX) 6 Associative rings and algebras (16-XX) 6 Approximations and expansions (41-XX) 5 Real functions (26-XX) 5 Dynamical systems and ergodic theory (37-XX) 4 History and biography (01-XX) 4 General algebraic systems (08-XX) 4 Topological groups, Lie groups (22-XX) 4 Fluid mechanics (76-XX) 3 General and overarching topics; collections (00-XX) 3 Category theory; homological algebra (18-XX) 3 Measure and integration (28-XX) 3 Functions of a complex variable (30-XX) 3 Ordinary differential equations (34-XX) 3 Partial differential equations (35-XX) 2 Nonassociative rings and algebras (17-XX) 2 Several complex variables and analytic spaces (32-XX) 2 Differential geometry (53-XX) 2 Relativity and gravitational theory (83-XX) 1 Special functions (33-XX) 1 Abstract harmonic analysis (43-XX) 1 General topology (54-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of deformable solids (74-XX) 1 Optics, electromagnetic theory (78-XX) Citations by Year