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: Indexed cover-to-cover; Published electronic only as of Vol. 1 (2005). This journal is available open access. Documents Indexed: 295 Publications (since 2005) References Indexed: 183 Publications with 5,846 References. all top 5 Latest Issues 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 9 Aaronson, Scott 9 Lovett, Shachar 8 Wigderson, Avi 7 Dvir, Zeev 6 Bansal, Nikhil 6 Håstad, Johan Torkel 6 O’Donnell, Ryan 6 Servedio, Rocco A. 6 Srinivasan, Srikanth 5 Guruswami, Venkatesan 5 Mossel, Elchanan 5 Regev, Oded 5 Sherstov, Alexander A. 5 Shpilka, Amir 5 Vadhan, Salil P. 5 Viola, Emanuele 4 Ambainis, Andris 4 Chekuri, Chandra S. 4 Hrubeš, Pavel 4 Khot, Subhash Ajit 4 Kopparty, Swastik 4 Sudan, Madhu 4 Williams, Richard Ryan 3 Alon, Noga M. 3 Austrin, Per 3 Blum, Avrim L. 3 Briët, Jop 3 Bun, Mark 3 Chakrabarty, Deeparnab 3 Dadush, Daniel 3 De, Anindya K. 3 Feige, Uriel 3 Göös, Mika 3 Harsha, Prahladh 3 Huang, Sangxia 3 Krauthgamer, Robert 3 Kumar, Mrinal 3 Kuperberg, Gregory John 3 Makarychev, Yury S. 3 Manokaran, Rajsekar 3 Pitassi, Toniann 3 Raz, Ran 3 Ron-Zewi, Noga 3 Saks, Michael E. 3 Špalek, Robert 3 Srinivasan, Aravind 3 Svensson, Ola 3 Ta-Shma, Amnon 3 Thaler, Justin 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 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 Haviv, Ishay 2 Holenstein, Thomas 2 Jain, Rahul 2 Kamath, Pritish 2 Khanna, Sanjeev 2 Klivans, Adam R. 2 Kothari, Robin 2 Landsberg, Joseph Montague 2 Lee, Chin Ho 2 Lee, Euiwoong 2 Lee, Homin K. 2 Limaye, Nutan 2 Magen, Avner 2 Meka, Raghu 2 Micciancio, Daniele 2 Motwani, Rajeev 2 Murtagh, Jack 2 Nagarajan, Viswanath 2 Neeman, Joe 2 Rademacher, Luis A. 2 Raskhodnikova, Sofya ...and 363 more Authors all top 5 Fields 276 Computer science (68-XX) 46 Information and communication theory, circuits (94-XX) 33 Combinatorics (05-XX) 32 Operations research, mathematical programming (90-XX) 31 Quantum theory (81-XX) 16 Number theory (11-XX) 14 Mathematical logic and foundations (03-XX) 14 Probability theory and stochastic processes (60-XX) 14 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 12 General and overarching topics; collections (00-XX) 10 Linear and multilinear algebra; matrix theory (15-XX) 9 Order, lattices, ordered algebraic structures (06-XX) 8 Convex and discrete geometry (52-XX) 6 Numerical analysis (65-XX) 4 Field theory and polynomials (12-XX) 4 Harmonic analysis on Euclidean spaces (42-XX) 4 Statistics (62-XX) 3 Group theory and generalizations (20-XX) 2 History and biography (01-XX) 1 Commutative algebra (13-XX) 1 Algebraic geometry (14-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 209 Publications have been cited 1,663 times in 1,472 Documents Cited by ▼ Year ▼ Maximizing the spread of influence through a social network. Zbl 1337.91069Kempe, David; Kleinberg, Jon; Tardos, Éva 218 2015 Linear degree extractors and the inapproximability of max clique and chromatic number. Zbl 1213.68322Zuckerman, David 143 2007 The multiplicative weights update method: a meta-algorithm and applications. Zbl 1283.68414Arora, Sanjeev; Hazan, Elad; Kale, Satyen 77 2012 A quantum algorithm for the Hamiltonian NAND tree. Zbl 1213.68284Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam 61 2008 Can you beat treewidth? Zbl 1213.68316Marx, Dániel 43 2010 Approximate nearest neighbor: towards removing the curse of dimensionality. Zbl 1278.68344Har-Peled, Sariel; Indyk, Piotr; Motwani, Rajeev 29 2012 New lower bounds for the border rank of matrix multiplication. Zbl 1336.68102Landsberg, Joseph M.; Ottaviani, Giorgio 26 2015 Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Zbl 1213.68281Ambainis, Andris 25 2005 Inapproximability of vertex cover and independent set in bounded degree graphs. Zbl 1243.68183Austrin, Per; Khot, Subhash; Safra, Muli 25 2011 The computational complexity of linear optics. Zbl 1298.81046Aaronson, Scott; Arkhipov, Alex 24 2013 Quantum search of spatial regions. Zbl 1213.68279Aaronson, Scott; Ambainis, Andris 23 2005 An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Zbl 1213.68700Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce 22 2006 Near-optimal network design with selfish agents. Zbl 1213.68698Anshelevich, Elliot; Dasgupta, Anirban; Tardos, Éva; Wexler, Tom 22 2008 The projection games conjecture and the NP-hardness of \(\ln n\)-approximating Set-Cover. Zbl 1335.68097Moshkovitz, Dana 19 2015 Rank bounds and integrality gaps for cutting planes procedures. Zbl 1213.68328Buresh-Oppenheim, Joshua; Galesi, Nicola; Hoory, Shlomo; Magen, Avner; Pitassi, Toniann 19 2006 Separation of multilinear circuit and formula size. Zbl 1213.68301Raz, Ran 18 2006 Approximation algorithms and online mechanisms for item pricing. Zbl 1213.68699Balcan, Maria-Florina; Blum, Avrim 18 2007 Proving integrality gaps without knowing the linear program. Zbl 1213.68306Arora, Sanjeev; Bollobás, Béla; Lovász, László; Tourlakis, Iannis 17 2006 Near-optimal and explicit Bell inequality violations. Zbl 1298.81034Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald 16 2012 Distance transforms of sampled functions. Zbl 1280.68266Felzenszwalb, Pedro F.; Huttenlocher, Daniel P. 15 2012 Correlation clustering with a fixed number of clusters. Zbl 1213.68704Giotis, Ioannis; Guruswami, Venkatesan 14 2006 Norms, XOR lemmas, and lower bounds for polynomials and protocols. Zbl 1213.68321Viola, Emanuele; Wigderson, Avi 14 2008 Computing the partition function for cliques in a graph. Zbl 1351.05212Barvinok, Alexander 13 2015 How hard is it to approximate the Jones polynomial? Zbl 1337.68109Kuperberg, Greg 13 2015 Matrix approximation and projective clustering via volume sampling. Zbl 1213.68702Deshpande, Amit; Rademacher, Luis; Vempala, Santosh; Wang, Grant 12 2006 Elusive functions and lower bounds for arithmetic circuits. Zbl 1213.68318Raz, Ran 12 2010 A separation of NP and conp in multiparty communication complexity. Zbl 1213.68293Gavinsky, Dmitry; Sherstov, Alexander A. 12 2010 Locally checkable proofs in distributed computing. Zbl 1401.68085Göös, Mika; Suomela, Jukka 11 2016 The communication complexity of gap Hamming distance. Zbl 1253.68158Sherstov, Alexander A. 11 2012 Limitations of quantum advice and one-way communication. Zbl 1213.68278Aaronson, Scott 11 2005 Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Zbl 1213.68697Wigderson, Avi; Xiao, David 11 2008 Matchgates revisited. Zbl 1342.68156Cai, Jin-Yi; Gorenstein, Aaron 10 2014 Grothendieck inequalities for semidefinite programs with rank constraint. Zbl 1297.68261Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank 10 2014 Query efficient PCPs with perfect completeness. Zbl 1213.68331Håstad, Johan; Khot, Subhash 10 2005 An exponential separation between regular and general resolution. Zbl 1213.68303Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair 10 2007 Parallel repetition: simplification and the no-signaling case. Zbl 1213.68297Holenstein, Thomas 10 2009 The submodular welfare problem with demand queries. Zbl 1213.68703Feige, Uriel; Vondrák, Jan 10 2010 The need for structure in quantum speedups. Zbl 1298.81045Aaronson, Scott; Ambainis, Andris 9 2014 Regularity lemmas and combinatorial algorithms. Zbl 1253.68162Bansal, Nikhil; Williams, Ryan 9 2012 Quantum lower bound for the collision problem with small range. Zbl 1213.68286Kutin, Samuel 9 2005 Quantum fan-out is powerful. Zbl 1213.68298Høyer, Peter; Špalek, Robert 9 2005 The randomized communication complexity of set disjointness. Zbl 1213.68332Håstad, Johan; Wigderson, Avi 9 2007 The power of unentanglement. Zbl 1213.68280Aaronson, Scott; Beigi, Salman; Drucker, Andrew; Fefferman, Bill; Shor, Peter 9 2009 Quantum expanders: motivation and construction. Zbl 1213.81052Ben-Aroya, Avraham; Schwartz, Oded; Ta-Shma, Amnon 9 2010 An optimal lower bound for monotonicity testing over hypergrids. Zbl 1319.68098Chakrabarty, Deeparnab; Seshadhri, C. 8 2014 List-decoding multiplicity codes. Zbl 1397.94127Kopparty, Swastik 8 2015 Anti-concentration for polynomials of independent random variables. Zbl 1392.68193Meka, Raghu; Nguyen, Oanh; Vu, Van 8 2016 Revenue submodularity. Zbl 1246.91054Dughmi, Shaddin; Roughgarden, Tim; Sundararajan, Mukund 8 2012 Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152Haviv, Ishay; Regev, Oded 8 2012 The one-way communication complexity of Hamming distance. Zbl 1213.68334Jayram, T. S.; Kumar, Ravi; Sivakumar, D. 8 2008 Unconditional pseudorandom generators for low degree polynomials. Zbl 1213.68274Lovett, Shachar 8 2009 Discrete-query quantum algorithm for NAND trees. Zbl 1213.68283Childs, Andrew M.; Cleve, Richard; Jordan, Stephen P.; Yonge-Mallo, David 8 2009 Semidefinite programs for completely bounded norms. Zbl 1213.81047Watrous, John 8 2009 Tensor products of weakly smooth codes are robust. Zbl 1213.68252Ben-Sasson, Eli; Viderman, Michael 8 2009 Monotone expanders: constructions and applications. Zbl 1213.68440Dvir, Zeev; Wigderson, Avi 8 2010 Tight bounds on the average sensitivity of k-CNF. Zbl 1213.68416Amano, Kazuyuki 8 2011 Conditional random fields, planted constraint satisfaction, and entropy concentration. Zbl 1351.68190Abbe, Emmanuel; Montanari, Andrea 7 2015 Non-commutative arithmetic circuits with division. Zbl 1403.94130Hrubeš, Pavel; Wigderson, Avi 7 2015 Solving packing integer programs via randomized rounding with alterations. Zbl 1297.68259Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind 7 2012 Inapproximability of NP-complete variants of Nash equilibrium. Zbl 1366.68071Austrin, Per; Braverman, Mark; Chlamtáč, Eden 7 2013 Making polynomials robust to noise. Zbl 1366.68063Sherstov, Alexander A. 7 2013 Approximating the AND-OR tree. Zbl 1328.68078Sherstov, Alexander A. 7 2013 An \(O(k^3\log n)\)-approximation algorithm for vertex-connectivity survivable network design. Zbl 1253.68167Chuzhoy, Julia; Khanna, Sanjeev 7 2012 All quantum adversary methods are equivalent. Zbl 1213.68289Špalek, Robert; Szegedy, Mario 7 2006 Iterative construction of Cayley expander graphs. Zbl 1213.05127Rozenman, Eyal; Shalev, Aner; Wigderson, Avi 7 2006 Quantum versus classical proofs and advice. Zbl 1213.68290Aaronson, Scott; Kuperberg, Greg 7 2007 Approximation algorithms for unique games. Zbl 1213.68320Trevisan, Luca 7 2008 On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity. Zbl 1378.68053Murray, Cody D.; Williams, R. Ryan 7 2017 Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122Briët, Jop; Regev, Oded; Saket, Rishi 7 2017 The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Zbl 1366.68073Gottesman, Daniel; Irani, Sandy 6 2013 Pseudorandomness for width-2 branching programs. Zbl 1300.68037Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir 6 2013 SDP gaps from pairwise independence. Zbl 1253.68141Benabbas, Siavosh; Georgiou, Konstantinos; Magen, Avner; Tulsiani, Madhur 6 2012 Span-program-based quantum algorithm for evaluating formulas. Zbl 1279.68097Reichardt, Ben; Špalek, Robert 6 2012 A non-linear time lower bound for Boolean branching programs. Zbl 1213.68302Ajtai, Miklós 6 2005 How to verify a quantum computation. Zbl 1395.68142Broadbent, Anne 6 2018 Width-parametrized SAT: time-space tradeoffs. Zbl 1319.68094Allender, Eric; Chen, Shiteng; Lou, Tiancheng; Papakonstantinou, Periklis A.; Tang, Bangsheng 5 2014 The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122Faben, John; Jerrum, Mark 5 2015 Circumventing \(d\)-to-\(1\) for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Zbl 1366.68084Wenner, Cenny 5 2013 Hardness of vertex deletion and project scheduling. Zbl 1366.68083Svensson, Ola 5 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 5 2014 Bounding the sensitivity of polynomial threshold functions. Zbl 1366.68096Harsha, Prahladh; Klivans, Adam; Meka, Raghu 5 2014 Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states. Zbl 1362.68087McKague, Matthew 5 2016 A tradeoff between length and width in resolution. Zbl 1355.03047Thapen, Neil 5 2016 On the hardness of learning with errors with binary secrets. Zbl 1412.68072Micciancio, Daniele 5 2018 Quantum-walk speedup of backtracking algorithms. Zbl 1417.68046Montanaro, Ashley 5 2018 Lower bounds for non-commutative skew circuits. Zbl 1393.68063Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth 5 2016 Inverse conjecture for the Gowers norm is false. Zbl 1282.11009Lovett, Shachar; Meshulam, Roy; Samorodnitsky, Alex 5 2011 On circuit lower bounds from derandomization. Zbl 1247.68091Aaronson, Scott; van Melkebeek, Dieter 5 2011 Time-space efficient simulations of quantum computations. Zbl 1253.68136Van Melkebeek, Dieter; Watson, Thomas 5 2012 Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1253.68068Bansal, Nikhil; Chan, Ho-Leung; Katz, Dmitriy; Pruhs, Kirk 5 2012 Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1255.68303Guruswami, Venkatesan; Zhou, Yuan 5 2012 Inapproximability of the shortest vector problem: toward a deterministic reduction. Zbl 1282.68127Micciancio, Daniele 5 2012 Testing linear-invariant non-linear properties. Zbl 1246.68259Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 5 2011 Learning \(k\)-modal distributions via testing. Zbl 1319.68119Daskalakis, Constantinos; Diakonikolas, Ilias; Servedio, Rocco A. 4 2014 On reconstruction and testing of read-once formulas. Zbl 1319.68113Shpilka, Amir; Volkovich, Ilya 4 2014 The power of nondeterminism in self-assembly. Zbl 1366.68054Bryans, Nathaniel; Chiniforooshan, Ehsan; Doty, David; Kari, Lila; Seki, Shinnosuke 4 2013 The complexity of the fermionant and immanants of constant width. Zbl 1366.68078Mertens, Stephan; Moore, Cristopher 4 2013 Lower bounds for the average and smoothed number of Pareto-optima. Zbl 1354.90126Brunsch, Tobias; Goyal, Navin; Rademacher, Luis; Röglin, Heiko 4 2014 Communication complexity of set-disjointness for all probabilities. Zbl 1365.68259Göös, Mika; Watson, Thomas 4 2016 Learning restricted models of arithmetic circuits. Zbl 1213.68341Klivans, Adam; Shpilka, Amir 4 2006 Limits on the universal method for matrix multiplication. Zbl 07413496Alman, Josh 1 2021 Barriers for fast matrix multiplication from irreversibility. Zbl 07413497Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen 1 2021 The polynomial method strikes back: tight quantum query bounds via dual polynomials. Zbl 1462.68060Bun, Mark; Kothari, Robin; Thaler, Justin 2 2020 Relaxed locally correctable codes. Zbl 1477.68110Gur, Tom; Ramnarayan, Govind; Rothblum, Ron 1 2020 Fourier and circulant matrices are not rigid. Zbl 1477.68117Dvir, Zeev; Liu, Allen 1 2020 On the hardness of approximate and exact (bichromatic) maximum inner product. Zbl 1462.68067Chen, Lijie 1 2020 On the hardness of approximating the \(k\)-Way Hypergraph Cut problem. Zbl 1462.68066Chekuri, Chandra; Li, Shi 1 2020 Matrix rigidity and the Croot-Lev-Pach lemma. Zbl 1477.68116Dvir, Zeev; Edelman, Benjamin L. 2 2019 Closure results for polynomial factorization. Zbl 1477.68106Chou, Chi-Ning; Kumar, Mrinal; Solomon, Noam 2 2019 Algebraic dependencies and \(\mathsf{PSPACE}\) algorithms in approximative complexity over any field. Zbl 1456.68058Guo, Zeyu; Saxena, Nitin; Sinhababu, Amit 2 2019 Potential-function proofs for gradient methods. Zbl 1482.90145Bansal, Nikhil; Gupta, Anupam 1 2019 Outlaw distributions and locally decodable codes. Zbl 1477.94080Briët, Jop; Dvir, Zeev; Gopi, Sivakanth 1 2019 Subsets of Cayley graphs that induce many edges. Zbl 07166714Gowers, Timothy; Janzer, Oliver 1 2019 How to verify a quantum computation. Zbl 1395.68142Broadbent, Anne 6 2018 On the hardness of learning with errors with binary secrets. Zbl 1412.68072Micciancio, Daniele 5 2018 Quantum-walk speedup of backtracking algorithms. Zbl 1417.68046Montanaro, Ashley 5 2018 Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth 3 2018 Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression. Zbl 1412.68071Kopparty, Swastik; Srinivasan, Srikanth 2 2018 New algorithms and lower bounds for circuits with linear threshold gates. Zbl 1410.68127Williams, R. Ryan 2 2018 Randomized query complexity of sabotaged and composed functions. Zbl 1398.68186Ben-David, Shalev; Kothari, Robin 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 1 2018 Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Zbl 1412.68081Forbes, Michael A.; Shpilka, Amir; Volk, Ben Lee 1 2018 Simplified separation of information and communication. Zbl 1412.68060Rao, Anup; Sinha, Makrand 1 2018 Separation of unbounded-error models in multi-party communication complexity. Zbl 1414.68027Chattopadhyay, Arkadev; Mande, Nikhil S. 1 2018 On multiparty communication with large versus unbounded error. Zbl 1412.68061Sherstov, Alexander A. 1 2018 A deterministic PTAS for the commutative rank of matrix spaces. Zbl 1395.68333Bläser, Markus; Jindal, Gorav; Pandey, Anurag 1 2018 Linear-time algorithm for quantum 2SAT. Zbl 1395.68132Arad, Itai; Santha, Miklos; Sundaram, Aarthi; Zhang, Shengyu 1 2018 The complexity of computing the optimal composition of differential privacy. Zbl 1395.94305Murtagh, Jack; Vadhan, Salil 1 2018 Trading information complexity for error. Zbl 1394.68148Dagan, Yuval; Filmus, Yuval; Hatami, Hamed; Li, Yaqiao 1 2018 On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity. Zbl 1378.68053Murray, Cody D.; Williams, R. Ryan 7 2017 Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122Briët, Jop; Regev, Oded; Saket, Rishi 7 2017 Superquadratic lower bound for 3-query locally correctable codes over the reals. Zbl 1375.94176Dvir, Zeev; Saraf, Shubhangi; Wigderson, Avi 2 2017 Some limitations of the sum of small-bias distributions. Zbl 1387.68125Lee, Chin Ho; Viola, Emanuele 2 2017 A communication game related to the sensitivity conjecture. Zbl 1379.68151Gilmer, Justin; Koucký, Michal; Saks, Michael 1 2017 Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Zbl 1378.68080Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin 1 2017 Nash equilibria in perturbation-stable games. Zbl 1380.91011Balcan, Maria-Florina; Braverman, Mark 1 2017 Pseudorandomness and Fourier-growth bounds for width-3 branching programs. Zbl 1377.65003Steinke, Thomas; Vadhan, Salil; Wan, Andrew 1 2017 The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems. Zbl 1387.68127Shepherd, F. Bruce; Vetta, Adrian R. 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 11 2016 Anti-concentration for polynomials of independent random variables. Zbl 1392.68193Meka, Raghu; Nguyen, Oanh; Vu, Van 8 2016 Interactive proofs for \(\mathsf{BQP}\) via self-tested graph states. Zbl 1362.68087McKague, Matthew 5 2016 A tradeoff between length and width in resolution. Zbl 1355.03047Thapen, Neil 5 2016 Lower bounds for non-commutative skew circuits. Zbl 1393.68063Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth 5 2016 Communication complexity of set-disjointness for all probabilities. Zbl 1365.68259Göös, Mika; Watson, Thomas 4 2016 Lattice sparsification and the approximate closest vector problem. Zbl 1362.68291Dadush, Daniel; Kun, Gábor 3 2016 Dual polynomials for collision and element distinctness. Zbl 1393.68055Bun, Mark; Thaler, Justin 3 2016 Private learning and sanitization: pure vs. approximate differential privacy. Zbl 1362.68096Beimel, Amos; Nissim, Kobbi; Stemmer, Uri 2 2016 Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11080Kopparty, Swastik; Kumar, Mrinal; Saks, Michael 2 2016 Simple proof of hardness of feedback vertex set. Zbl 1343.68095Guruswami, Venkatesan; Lee, Euiwoong 2 2016 Lowest-degree \(k\)-spanner: approximation and hardness. Zbl 1393.68187Chlamtáč, Eden; Dinitz, Michael 2 2016 Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. Zbl 1353.81035Lin, Cedric Yen-Yu; Lin, Han-Hsuan 1 2016 Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion. Zbl 1393.68190Louis, Anand; Makarychev, Yury 1 2016 Minimizing maximum flow-time on related machines. Zbl 1391.90239Bansal, Nikhil; Cloostermans, Bouke 1 2016 Robust lower bounds for communication and stream computation. Zbl 1392.68191Chakrabarti, Amit; Cormode, Graham; Mcgregor, Andrew 1 2016 Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V. 1 2016 Maximizing the spread of influence through a social network. Zbl 1337.91069Kempe, David; Kleinberg, Jon; Tardos, Éva 218 2015 New lower bounds for the border rank of matrix multiplication. Zbl 1336.68102Landsberg, Joseph M.; Ottaviani, Giorgio 26 2015 The projection games conjecture and the NP-hardness of \(\ln n\)-approximating Set-Cover. Zbl 1335.68097Moshkovitz, Dana 19 2015 Computing the partition function for cliques in a graph. Zbl 1351.05212Barvinok, Alexander 13 2015 How hard is it to approximate the Jones polynomial? Zbl 1337.68109Kuperberg, Greg 13 2015 List-decoding multiplicity codes. Zbl 1397.94127Kopparty, Swastik 8 2015 Conditional random fields, planted constraint satisfaction, and entropy concentration. Zbl 1351.68190Abbe, Emmanuel; Montanari, Andrea 7 2015 Non-commutative arithmetic circuits with division. Zbl 1403.94130Hrubeš, Pavel; Wigderson, Avi 7 2015 The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122Faben, John; Jerrum, Mark 5 2015 Adapt or die: polynomial lower bounds for non-adaptive dynamic data structures. Zbl 1351.68084Brody, Joshua; Larsen, Kasper Green 3 2015 On some extensions of the FKN theorem. Zbl 1352.60029Jendrej, Jacek; Oleszkiewicz, Krzysztof; Wojtaszczyk, Jakub O. 3 2015 Quantum algorithm for monotonicity testing on the hypercube. Zbl 1351.68105Belovs, Aleksandrs; Blais, Eric 3 2015 Quantum interactive proofs and the complexity of separability testing. Zbl 1336.68082Gutoski, Gus; Hayden, Patrick; Milner, Kevin; Wilde, Mark M. 3 2015 On the NP-hardness of approximating ordering-constraint satisfaction problems. Zbl 1335.68094Austrin, Per; Manokaran, Rajsekar; Wenner, Cenny 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 Matchgates revisited. Zbl 1342.68156Cai, Jin-Yi; Gorenstein, Aaron 10 2014 Grothendieck inequalities for semidefinite programs with rank constraint. Zbl 1297.68261Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank 10 2014 The need for structure in quantum speedups. Zbl 1298.81045Aaronson, Scott; Ambainis, Andris 9 2014 An optimal lower bound for monotonicity testing over hypergrids. Zbl 1319.68098Chakrabarty, Deeparnab; Seshadhri, C. 8 2014 Width-parametrized SAT: time-space tradeoffs. Zbl 1319.68094Allender, Eric; Chen, Shiteng; Lou, Tiancheng; Papakonstantinou, Periklis A.; Tang, Bangsheng 5 2014 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 5 2014 Bounding the sensitivity of polynomial threshold functions. Zbl 1366.68096Harsha, Prahladh; Klivans, Adam; Meka, Raghu 5 2014 Learning \(k\)-modal distributions via testing. Zbl 1319.68119Daskalakis, Constantinos; Diakonikolas, Ilias; Servedio, Rocco A. 4 2014 On reconstruction and testing of read-once formulas. Zbl 1319.68113Shpilka, Amir; Volkovich, Ilya 4 2014 Lower bounds for the average and smoothed number of Pareto-optima. Zbl 1354.90126Brunsch, Tobias; Goyal, Navin; Rademacher, Luis; Röglin, Heiko 4 2014 Approximation algorithm for non-Boolean Max-\(k\)-CSP. Zbl 1319.68254Makarychev, Konstantin; Makarychev, Yury 3 2014 Tight bounds for monotone switching networks via Fourier analysis. Zbl 1319.68100Chan, Siu Man; Potechin, Aaron 2 2014 Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323Naor, Assaf; Regev, Oded; Vidick, Thomas 2 2014 Improved inapproximability for TSP. Zbl 1366.68077Lampis, Michael 2 2014 Dimension-free \(L_2\) maximal inequality for spherical means in the hypercube. Zbl 1298.42022Harrow, Aram W.; Kolla, Alexandra; Schulman, Leonard J. 2 2014 Approximation resistance on satisfiable instances for predicates with few accepting inputs. Zbl 1319.68111Huang, Sangxia 1 2014 Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. Zbl 1366.68068Allender, Eric; Lange, Klaus-Jörn 1 2014 The computational complexity of linear optics. Zbl 1298.81046Aaronson, Scott; Arkhipov, Alex 24 2013 Inapproximability of NP-complete variants of Nash equilibrium. Zbl 1366.68071Austrin, Per; Braverman, Mark; Chlamtáč, Eden 7 2013 Making polynomials robust to noise. Zbl 1366.68063Sherstov, Alexander A. 7 2013 Approximating the AND-OR tree. Zbl 1328.68078Sherstov, Alexander A. 7 2013 The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Zbl 1366.68073Gottesman, Daniel; Irani, Sandy 6 2013 Pseudorandomness for width-2 branching programs. Zbl 1300.68037Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir 6 2013 Circumventing \(d\)-to-\(1\) for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Zbl 1366.68084Wenner, Cenny 5 2013 Hardness of vertex deletion and project scheduling. Zbl 1366.68083Svensson, Ola 5 2013 The power of nondeterminism in self-assembly. Zbl 1366.68054Bryans, Nathaniel; Chiniforooshan, Ehsan; Doty, David; Kari, Lila; Seki, Shinnosuke 4 2013 The complexity of the fermionant and immanants of constant width. Zbl 1366.68078Mertens, Stephan; Moore, Cristopher 4 2013 Constructing small-bias sets from algebraic-geometric codes. Zbl 1345.94103Ben-Aroya, Avraham; Ta-Shma, Amnon 3 2013 ...and 109 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 2,642 Authors 13 Guruswami, Venkatesan 12 Hoefer, Martin 12 Wu, Weili 10 Bonnet, Edouard 10 Palazuelos, Carlos 9 Gargano, Luisa 9 Lampis, Michael 9 Sherstov, Alexander A. 8 Ambainis, Andris 8 Goldberg, Leslie Ann 8 Grigorescu, Elena 8 Marx, Dániel 8 Miyano, Eiji 8 Pitassi, Toniann 8 Rautenbach, Dieter 8 Srinivasan, Srikanth 8 Thaler, Justin 8 Viola, Emanuele 7 Aaronson, Scott 7 Allender, Eric W. 7 Bazgan, Cristina 7 Bun, Mark 7 Chekuri, Chandra S. 7 Childs, Andrew M. 7 Cordasco, Gennaro 7 Huang, Chien-Chung 7 Le Gall, François 7 Mahajan, Meena 7 Naor, Assaf 7 Paschos, Vangelis Th. 7 Pokutta, Sebastian 7 Rescigno, Adele Anna 7 Tuza, Zsolt 7 Wiese, Andreas 7 Wigderson, Avi 6 Barvinok, Alexander I. 6 Belovs, Aleksandrs 6 Briët, Jop 6 Cai, Jin-Yi 6 Chalermsook, Parinya 6 Elbassioni, Khaled M. 6 Khot, Subhash Ajit 6 Landsberg, Joseph Montague 6 Limaye, Nutan 6 Makino, Kazuhisa 6 Massarenti, Alex 6 Roughgarden, Tim 6 Servedio, Rocco A. 6 Shpilka, Amir 6 Sikora, Florian 6 Tzameret, Iddo 6 Vaccaro, Ugo 6 van Melkebeek, Dieter 6 Yoshida, Yuichi 5 Alon, Noga M. 5 Asahiro, Yuichi 5 Ben-Sasson, Eli 5 Borodin, Allan B. 5 Braverman, Mark 5 Christandl, Matthias 5 Chuzhoy, Julia 5 D’Angelo, Gianlorenzo 5 Dantchev, Stefan Stoyanov 5 Deligkas, Argyrios 5 Fearnley, John 5 Filmus, Yuval 5 Fiorini, Samuel 5 Fu, Bin 5 Fu, Zhiguo 5 Gur, Tom 5 Halldórsson, Magnús Mar 5 Harrow, Aram Wettroth 5 Im, Sungjin 5 Impagliazzo, Russell 5 Jansson, Jesper 5 Manurangsi, Pasin 5 Martin, Barnaby D. 5 Nishimura, Harumichi 5 Ordyniak, Sebastian 5 Porat, Ely 5 Qiao, Youming 5 Raz, Ran 5 Regev, Oded 5 Regts, Guus 5 Reichman, Daniel 5 Santha, Miklos 5 Shapira, Asaf 5 Spirakis, Paul G. 5 Suchý, Ondřej 5 Thai, My T. 5 Viderman, Michael 5 Vidick, Thomas 5 Wong, Thomas G. 4 Abbe, Emmanuel 4 Anshelevich, Elliot 4 Bansal, Nikhil 4 Bausch, Johannes 4 Brandão, Fernando G. S. L. 4 Brody, Joshua E. 4 Caragiannis, Ioannis ...and 2,542 more Authors all top 5 Cited in 256 Journals 93 SIAM Journal on Computing 93 Theoretical Computer Science 91 Algorithmica 63 Computational Complexity 40 Discrete Applied Mathematics 34 Theory of Computing Systems 30 Journal of Combinatorial Optimization 27 SIAM Journal on Discrete Mathematics 26 Journal of Computer and System Sciences 25 Information Processing Letters 22 Quantum Information Processing 20 Mathematical Programming. Series A. Series B 20 Discrete Optimization 17 Communications in Mathematical Physics 16 Information and Computation 14 Journal of Mathematical Physics 11 Combinatorica 11 Journal of the ACM 10 Information Sciences 10 Distributed Computing 10 Journal of Machine Learning Research (JMLR) 9 Discrete & Computational Geometry 9 Random Structures & Algorithms 9 Data Mining and Knowledge Discovery 8 Israel Journal of Mathematics 8 New Journal of Physics 7 Artificial Intelligence 7 Discrete Mathematics 7 Journal of Statistical Physics 7 Mathematics of Operations Research 7 Annals of Operations Research 7 The Electronic Journal of Combinatorics 7 Internet Mathematics 7 Theory of Computing 7 Discrete Analysis 6 Operations Research 6 Operations Research Letters 6 Computational Optimization and Applications 5 European Journal of Combinatorics 5 Journal of Cryptology 5 Journal of Global Optimization 5 Games and Economic Behavior 5 Linear Algebra and its Applications 5 SIAM Journal on Optimization 5 Annales Henri Poincaré 5 Discrete Mathematics, Algorithms and Applications 4 International Journal of Theoretical Physics 4 Physica A 4 Physics Letters. A 4 Automatica 4 Machine Learning 4 Geometric and Functional Analysis. GAFA 4 European Journal of Operational Research 4 Bulletin of the American Mathematical Society. New Series 4 Chicago Journal of Theoretical Computer Science 4 International Journal of Quantum Information 4 Algorithms 3 Applied Mathematics and Computation 3 Computing 3 Journal of Combinatorial Theory. Series B 3 Journal of Pure and Applied Algebra 3 Networks 3 Proceedings of the American Mathematical Society 3 SIAM Journal on Control and Optimization 3 Annals of Pure and Applied Logic 3 Graphs and Combinatorics 3 Journal of Symbolic Computation 3 Probability Theory and Related Fields 3 Computers & Operations Research 3 SIAM Review 3 Cybernetics and Systems Analysis 3 Combinatorics, Probability and Computing 3 The Journal of Artificial Intelligence Research (JAIR) 3 Annals of Mathematics and Artificial Intelligence 3 Foundations of Computational Mathematics 3 Journal of Discrete Algorithms 3 Foundations of Physics 3 Journal of Physics A: Mathematical and Theoretical 3 ACM Transactions on Algorithms 3 Games 3 Diskretnyĭ Analiz i Issledovanie Operatsiĭ 3 Journal of the Operations Research Society of China 3 Computer Science Review 3 ACM Transactions on Computation Theory 3 SIAM Journal on Applied Algebra and Geometry 2 Computer Physics Communications 2 Journal of Computational Physics 2 Linear and Multilinear Algebra 2 Physics Reports 2 Advances in Mathematics 2 The Annals of Probability 2 Journal of Algebra 2 Journal of Computational and Applied Mathematics 2 Journal of Functional Analysis 2 Mathematische Annalen 2 Journal of Computer Science and Technology 2 SIAM Journal on Matrix Analysis and Applications 2 Neural Computation 2 International Journal of Algebra and Computation 2 MSCS. Mathematical Structures in Computer Science ...and 156 more Journals all top 5 Cited in 49 Fields 936 Computer science (68-XX) 355 Combinatorics (05-XX) 291 Operations research, mathematical programming (90-XX) 217 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 191 Quantum theory (81-XX) 132 Information and communication theory, circuits (94-XX) 62 Probability theory and stochastic processes (60-XX) 52 Linear and multilinear algebra; matrix theory (15-XX) 46 Mathematical logic and foundations (03-XX) 38 Numerical analysis (65-XX) 37 Statistics (62-XX) 32 Number theory (11-XX) 29 Statistical mechanics, structure of matter (82-XX) 28 Functional analysis (46-XX) 23 Biology and other natural sciences (92-XX) 21 Group theory and generalizations (20-XX) 19 Algebraic geometry (14-XX) 19 Convex and discrete geometry (52-XX) 18 Order, lattices, ordered algebraic structures (06-XX) 13 Operator theory (47-XX) 10 Commutative algebra (13-XX) 9 Harmonic analysis on Euclidean spaces (42-XX) 9 Manifolds and cell complexes (57-XX) 8 Field theory and polynomials (12-XX) 7 Calculus of variations and optimal control; optimization (49-XX) 5 Approximations and expansions (41-XX) 4 History and biography (01-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Geometry (51-XX) 4 Systems theory; control (93-XX) 3 General algebraic systems (08-XX) 3 Associative rings and algebras (16-XX) 3 Category theory; homological algebra (18-XX) 3 Topological groups, Lie groups (22-XX) 3 Measure and integration (28-XX) 3 Ordinary differential equations (34-XX) 3 Partial differential equations (35-XX) 2 General and overarching topics; collections (00-XX) 2 Nonassociative rings and algebras (17-XX) 2 Real functions (26-XX) 2 Functions of a complex variable (30-XX) 2 Several complex variables and analytic spaces (32-XX) 2 Differential geometry (53-XX) 2 Fluid mechanics (76-XX) 1 Special functions (33-XX) 1 Abstract harmonic analysis (43-XX) 1 General topology (54-XX) 1 Mechanics of deformable solids (74-XX) 1 Relativity and gravitational theory (83-XX) Citations by Year