## 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: 302 Publications (since 2005) References Indexed: 190 Publications with 6,028 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 7 Servedio, Rocco A. 6 Bansal, Nikhil 6 Håstad, Johan Torkel 6 O’Donnell, Ryan 6 Srinivasan, Srikanth 5 Guruswami, Venkatesan 5 Khot, Subhash Ajit 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 Feige, Uriel 4 Hrubeš, Pavel 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 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 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 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 ...and 370 more Authors
all top 5

### Fields

 283 Computer science (68-XX) 46 Information and communication theory, circuits (94-XX) 34 Combinatorics (05-XX) 32 Operations research, mathematical programming (90-XX) 31 Quantum theory (81-XX) 16 Number theory (11-XX) 15 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) 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 Group theory and generalizations (20-XX) 4 Harmonic analysis on Euclidean spaces (42-XX) 4 Statistics (62-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)

### Citations contained in zbMATH Open

209 Publications have been cited 1,668 times in 1,477 Documents Cited by Year
Maximizing the spread of influence through a social network. Zbl 1337.91069
Kempe, David; Kleinberg, Jon; Tardos, Éva
2015
Linear degree extractors and the inapproximability of max clique and chromatic number. Zbl 1213.68322
Zuckerman, David
2007
The multiplicative weights update method: a meta-algorithm and applications. Zbl 1283.68414
Arora, Sanjeev; Hazan, Elad; Kale, Satyen
2012
A quantum algorithm for the Hamiltonian NAND tree. Zbl 1213.68284
Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam
2008
Can you beat treewidth? Zbl 1213.68316
Marx, Dániel
2010
Approximate nearest neighbor: towards removing the curse of dimensionality. Zbl 1278.68344
Har-Peled, Sariel; Indyk, Piotr; Motwani, Rajeev
2012
New lower bounds for the border rank of matrix multiplication. Zbl 1336.68102
Landsberg, Joseph M.; Ottaviani, Giorgio
2015
Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range. Zbl 1213.68281
Ambainis, Andris
2005
Inapproximability of vertex cover and independent set in bounded degree graphs. Zbl 1243.68183
Austrin, Per; Khot, Subhash; Safra, Muli
2011
The computational complexity of linear optics. Zbl 1298.81046
Aaronson, Scott; Arkhipov, Alex
2013
Quantum search of spatial regions. Zbl 1213.68279
Aaronson, Scott; Ambainis, Andris
2005
An $$O(\sqrt{n})$$ approximation and integrality gap for disjoint paths and unsplittable flow. Zbl 1213.68700
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce
2006
Near-optimal network design with selfish agents. Zbl 1213.68698
Anshelevich, Elliot; Dasgupta, Anirban; Tardos, Éva; Wexler, Tom
2008
The projection games conjecture and the NP-hardness of $$\ln n$$-approximating Set-Cover. Zbl 1335.68097
Moshkovitz, Dana
2015
Rank bounds and integrality gaps for cutting planes procedures. Zbl 1213.68328
Buresh-Oppenheim, Joshua; Galesi, Nicola; Hoory, Shlomo; Magen, Avner; Pitassi, Toniann
2006
Separation of multilinear circuit and formula size. Zbl 1213.68301
Raz, Ran
2006
Approximation algorithms and online mechanisms for item pricing. Zbl 1213.68699
Balcan, Maria-Florina; Blum, Avrim
2007
Proving integrality gaps without knowing the linear program. Zbl 1213.68306
Arora, Sanjeev; Bollobás, Béla; Lovász, László; Tourlakis, Iannis
2006
Near-optimal and explicit Bell inequality violations. Zbl 1298.81034
Buhrman, Harry; Regev, Oded; Scarpa, Giannicola; de Wolf, Ronald
2012
Distance transforms of sampled functions. Zbl 1280.68266
Felzenszwalb, Pedro F.; Huttenlocher, Daniel P.
2012
Correlation clustering with a fixed number of clusters. Zbl 1213.68704
Giotis, Ioannis; Guruswami, Venkatesan
2006
Norms, XOR lemmas, and lower bounds for polynomials and protocols. Zbl 1213.68321
Viola, Emanuele; Wigderson, Avi
2008
How hard is it to approximate the Jones polynomial? Zbl 1337.68109
Kuperberg, Greg
2015
Computing the partition function for cliques in a graph. Zbl 1351.05212
Barvinok, Alexander
2015
Matrix approximation and projective clustering via volume sampling. Zbl 1213.68702
Deshpande, Amit; Rademacher, Luis; Vempala, Santosh; Wang, Grant
2006
Elusive functions and lower bounds for arithmetic circuits. Zbl 1213.68318
Raz, Ran
2010
A separation of NP and conp in multiparty communication complexity. Zbl 1213.68293
Gavinsky, Dmitry; Sherstov, Alexander A.
2010
Locally checkable proofs in distributed computing. Zbl 1401.68085
Göös, Mika; Suomela, Jukka
2016
Limitations of quantum advice and one-way communication. Zbl 1213.68278
Aaronson, Scott
2005
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Zbl 1213.68697
Wigderson, Avi; Xiao, David
2008
The communication complexity of gap Hamming distance. Zbl 1253.68158
Sherstov, Alexander A.
2012
Matchgates revisited. Zbl 1342.68156
Cai, Jin-Yi; Gorenstein, Aaron
2014
Grothendieck inequalities for semidefinite programs with rank constraint. Zbl 1297.68261
Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank
2014
Query efficient PCPs with perfect completeness. Zbl 1213.68331
2005
An exponential separation between regular and general resolution. Zbl 1213.68303
Alekhnovich, Michael; Johannsen, Jan; Pitassi, Toniann; Urquhart, Alasdair
2007
Parallel repetition: simplification and the no-signaling case. Zbl 1213.68297
Holenstein, Thomas
2009
The submodular welfare problem with demand queries. Zbl 1213.68703
Feige, Uriel; Vondrák, Jan
2010
The need for structure in quantum speedups. Zbl 1298.81045
Aaronson, Scott; Ambainis, Andris
2014
Quantum lower bound for the collision problem with small range. Zbl 1213.68286
Kutin, Samuel
2005
Quantum fan-out is powerful. Zbl 1213.68298
Høyer, Peter; Špalek, Robert
2005
The randomized communication complexity of set disjointness. Zbl 1213.68332
2007
The power of unentanglement. Zbl 1213.68280
Aaronson, Scott; Beigi, Salman; Drucker, Andrew; Fefferman, Bill; Shor, Peter
2009
Quantum expanders: motivation and construction. Zbl 1213.81052
Ben-Aroya, Avraham; Schwartz, Oded; Ta-Shma, Amnon
2010
Regularity lemmas and combinatorial algorithms. Zbl 1253.68162
Bansal, Nikhil; Williams, Ryan
2012
List-decoding multiplicity codes. Zbl 1397.94127
Kopparty, Swastik
2015
An optimal lower bound for monotonicity testing over hypergrids. Zbl 1319.68098
2014
The one-way communication complexity of Hamming distance. Zbl 1213.68334
Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
2008
Unconditional pseudorandom generators for low degree polynomials. Zbl 1213.68274
Lovett, Shachar
2009
Discrete-query quantum algorithm for NAND trees. Zbl 1213.68283
Childs, Andrew M.; Cleve, Richard; Jordan, Stephen P.; Yonge-Mallo, David
2009
Semidefinite programs for completely bounded norms. Zbl 1213.81047
Watrous, John
2009
Tensor products of weakly smooth codes are robust. Zbl 1213.68252
Ben-Sasson, Eli; Viderman, Michael
2009
Monotone expanders: constructions and applications. Zbl 1213.68440
Dvir, Zeev; Wigderson, Avi
2010
Tight bounds on the average sensitivity of k-CNF. Zbl 1213.68416
Amano, Kazuyuki
2011
Revenue submodularity. Zbl 1246.91054
Dughmi, Shaddin; Roughgarden, Tim; Sundararajan, Mukund
2012
Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Zbl 1253.68152
Haviv, Ishay; Regev, Oded
2012
Anti-concentration for polynomials of independent random variables. Zbl 1392.68193
Meka, Raghu; Nguyen, Oanh; Vu, Van
2016
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
2017
Solving packing integer programs via randomized rounding with alterations. Zbl 1297.68259
Bansal, Nikhil; Korula, Nitish; Nagarajan, Viswanath; Srinivasan, Aravind
2012
Inapproximability of NP-complete variants of Nash equilibrium. Zbl 1366.68071
Austrin, Per; Braverman, Mark; Chlamtáč, Eden
2013
Making polynomials robust to noise. Zbl 1366.68063
Sherstov, Alexander A.
2013
Approximating the AND-OR tree. Zbl 1328.68078
Sherstov, Alexander A.
2013
All quantum adversary methods are equivalent. Zbl 1213.68289
Špalek, Robert; Szegedy, Mario
2006
Iterative construction of Cayley expander graphs. Zbl 1213.05127
Rozenman, Eyal; Shalev, Aner; Wigderson, Avi
2006
Quantum versus classical proofs and advice. Zbl 1213.68290
Aaronson, Scott; Kuperberg, Greg
2007
Approximation algorithms for unique games. Zbl 1213.68320
Trevisan, Luca
2008
An $$O(k^3\log n)$$-approximation algorithm for vertex-connectivity survivable network design. Zbl 1253.68167
Chuzhoy, Julia; Khanna, Sanjeev
2012
On the (non) $$\mathsf{NP}$$-hardness of computing circuit complexity. Zbl 1378.68053
Murray, Cody D.; Williams, R. Ryan
2017
Conditional random fields, planted constraint satisfaction, and entropy concentration. Zbl 1351.68190
Abbe, Emmanuel; Montanari, Andrea
2015
Non-commutative arithmetic circuits with division. Zbl 1403.94130
Hrubeš, Pavel; Wigderson, Avi
2015
The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Zbl 1366.68073
Gottesman, Daniel; Irani, Sandy
2013
Pseudorandomness for width-2 branching programs. Zbl 1300.68037
Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir
2013
A non-linear time lower bound for Boolean branching programs. Zbl 1213.68302
Ajtai, Miklós
2005
Time-space efficient simulations of quantum computations. Zbl 1253.68136
Van Melkebeek, Dieter; Watson, Thomas
2012
SDP gaps from pairwise independence. Zbl 1253.68141
Benabbas, Siavosh; Georgiou, Konstantinos; Magen, Avner; Tulsiani, Madhur
2012
Span-program-based quantum algorithm for evaluating formulas. Zbl 1279.68097
Reichardt, Ben; Špalek, Robert
2012
How to verify a quantum computation. Zbl 1395.68142
2018
A tradeoff between length and width in resolution. Zbl 1355.03047
Thapen, Neil
2016
The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122
Faben, John; Jerrum, Mark
2015
On the hardness of learning with errors with binary secrets. Zbl 1412.68072
Micciancio, Daniele
2018
Quantum-walk speedup of backtracking algorithms. Zbl 1417.68046
Montanaro, Ashley
2018
Circumventing $$d$$-to-$$1$$ for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Zbl 1366.68084
Wenner, Cenny
2013
Hardness of vertex deletion and project scheduling. Zbl 1366.68083
Svensson, Ola
2013
A regularity lemma and low-weight approximators for low-degree polynomial threshold functions. Zbl 1366.68089
Diakonikolas, Ilias; Servedio, Rocco A.; Tan, Li-Yang; Wan, Andrew
2014
Bounding the sensitivity of polynomial threshold functions. Zbl 1366.68096
2014
Width-parametrized SAT: time-space tradeoffs. Zbl 1319.68094
Allender, Eric; Chen, Shiteng; Lou, Tiancheng; Papakonstantinou, Periklis A.; Tang, Bangsheng
2014
Testing linear-invariant non-linear properties. Zbl 1246.68259
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
2011
Inverse conjecture for the Gowers norm is false. Zbl 1282.11009
Lovett, Shachar; Meshulam, Roy; Samorodnitsky, Alex
2011
On circuit lower bounds from derandomization. Zbl 1247.68091
Aaronson, Scott; van Melkebeek, Dieter
2011
Improved bounds for speed scaling in devices obeying the cube-root rule. Zbl 1253.68068
Bansal, Nikhil; Chan, Ho-Leung; Katz, Dmitriy; Pruhs, Kirk
2012
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1255.68303
Guruswami, Venkatesan; Zhou, Yuan
2012
Inapproximability of the shortest vector problem: toward a deterministic reduction. Zbl 1282.68127
Micciancio, Daniele
2012
Interactive proofs for $$\mathsf{BQP}$$ via self-tested graph states. Zbl 1362.68087
McKague, Matthew
2016
Lower bounds for non-commutative skew circuits. Zbl 1393.68063
Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth
2016
Communication complexity of set-disjointness for all probabilities. Zbl 1365.68259
Göös, Mika; Watson, Thomas
2016
The power of nondeterminism in self-assembly. Zbl 1366.68054
Bryans, Nathaniel; Chiniforooshan, Ehsan; Doty, David; Kari, Lila; Seki, Shinnosuke
2013
The complexity of the fermionant and immanants of constant width. Zbl 1366.68078
Mertens, Stephan; Moore, Cristopher
2013
Almost $$k$$-wise vs. $$k$$-wise independent permutations, and uniformity for general group actions. Zbl 1297.68183
Alon, Noga; Lovett, Shachar
2013
Lower bounds for the average and smoothed number of Pareto-optima. Zbl 1354.90126
Brunsch, Tobias; Goyal, Navin; Rademacher, Luis; Röglin, Heiko
2014
Learning $$k$$-modal distributions via testing. Zbl 1319.68119
Daskalakis, Constantinos; Diakonikolas, Ilias; Servedio, Rocco A.
2014
On reconstruction and testing of read-once formulas. Zbl 1319.68113
Shpilka, Amir; Volkovich, Ilya
2014
Limits on the universal method for matrix multiplication. Zbl 07413496
Alman, Josh
2021
Barriers for fast matrix multiplication from irreversibility. Zbl 07413497
Christandl, Matthias; Vrana, Péter; Zuiddam, Jeroen
2021
The polynomial method strikes back: tight quantum query bounds via dual polynomials. Zbl 1462.68060
Bun, Mark; Kothari, Robin; Thaler, Justin
2020
On the hardness of approximate and exact (bichromatic) maximum inner product. Zbl 1462.68067
Chen, Lijie
2020
On the hardness of approximating the $$k$$-Way Hypergraph Cut problem. Zbl 1462.68066
Chekuri, Chandra; Li, Shi
2020
Relaxed locally correctable codes. Zbl 1477.68110
Gur, Tom; Ramnarayan, Govind; Rothblum, Ron
2020
Fourier and circulant matrices are not rigid. Zbl 1477.68117
Dvir, Zeev; Liu, Allen
2020
Algebraic dependencies and $$\mathsf{PSPACE}$$ algorithms in approximative complexity over any field. Zbl 1456.68058
Guo, Zeyu; Saxena, Nitin; Sinhababu, Amit
2019
Matrix rigidity and the Croot-Lev-Pach lemma. Zbl 1477.68116
Dvir, Zeev; Edelman, Benjamin L.
2019
Closure results for polynomial factorization. Zbl 1477.68106
Chou, Chi-Ning; Kumar, Mrinal; Solomon, Noam
2019
Subsets of Cayley graphs that induce many edges. Zbl 07166714
Gowers, Timothy; Janzer, Oliver
2019
Potential-function proofs for gradient methods. Zbl 1482.90145
Bansal, Nikhil; Gupta, Anupam
2019
Outlaw distributions and locally decodable codes. Zbl 1477.94080
Briët, Jop; Dvir, Zeev; Gopi, Sivakanth
2019
How to verify a quantum computation. Zbl 1395.68142
2018
On the hardness of learning with errors with binary secrets. Zbl 1412.68072
Micciancio, Daniele
2018
Quantum-walk speedup of backtracking algorithms. Zbl 1417.68046
Montanaro, Ashley
2018
Average-case lower bounds and satisfiability algorithms for small threshold circuits. Zbl 1395.68138
Chen, Ruiwen; Santhanam, Rahul; Srinivasan, Srikanth
2018
Randomized query complexity of sabotaged and composed functions. Zbl 1398.68186
Ben-David, Shalev; Kothari, Robin
2018
Certifying polynomials for $$\mathsf{AC}^0[\oplus]$$ circuits, with applications to lower bounds and circuit compression. Zbl 1412.68071
Kopparty, Swastik; Srinivasan, Srikanth
2018
New algorithms and lower bounds for circuits with linear threshold gates. Zbl 1410.68127
Williams, R. Ryan
2018
On the size of homogeneous and of depth-four formulas with low individual degree. Zbl 1410.68125
Kayal, Neeraj; Saha, Chandan; Tavenas, Sébastien
2018
Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Zbl 1412.68081
Forbes, Michael A.; Shpilka, Amir; Volk, Ben Lee
2018
Simplified separation of information and communication. Zbl 1412.68060
Rao, Anup; Sinha, Makrand
2018
Separation of unbounded-error models in multi-party communication complexity. Zbl 1414.68027
2018
On multiparty communication with large versus unbounded error. Zbl 1412.68061
Sherstov, Alexander A.
2018
A deterministic PTAS for the commutative rank of matrix spaces. Zbl 1395.68333
Bläser, Markus; Jindal, Gorav; Pandey, Anurag
2018
Linear-time algorithm for quantum 2SAT. Zbl 1395.68132
Arad, Itai; Santha, Miklos; Sundaram, Aarthi; Zhang, Shengyu
2018
The complexity of computing the optimal composition of differential privacy. Zbl 1395.94305
2018
Trading information complexity for error. Zbl 1394.68148
Dagan, Yuval; Filmus, Yuval; Hatami, Hamed; Li, Yaqiao
2018
Tight hardness of the non-commutative Grothendieck problem. Zbl 1387.68122
Briët, Jop; Regev, Oded; Saket, Rishi
2017
On the (non) $$\mathsf{NP}$$-hardness of computing circuit complexity. Zbl 1378.68053
Murray, Cody D.; Williams, R. Ryan
2017
Some limitations of the sum of small-bias distributions. Zbl 1387.68125
Lee, Chin Ho; Viola, Emanuele
2017
Superquadratic lower bound for 3-query locally correctable codes over the reals. Zbl 1375.94176
Dvir, Zeev; Saraf, Shubhangi; Wigderson, Avi
2017
The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems. Zbl 1387.68127
Shepherd, F. Bruce; Vetta, Adrian R.
2017
Monotone projection lower bounds from extended formulation lower bounds. Zbl 1383.68036
Grochow, Joshua A.
2017
Nash equilibria in perturbation-stable games. Zbl 1380.91011
Balcan, Maria-Florina; Braverman, Mark
2017
Pseudorandomness and Fourier-growth bounds for width-3 branching programs. Zbl 1377.65003
Steinke, Thomas; Vadhan, Salil; Wan, Andrew
2017
A communication game related to the sensitivity conjecture. Zbl 1379.68151
Gilmer, Justin; Koucký, Michal; Saks, Michael
2017
Identity testing for constant-width, and any-order, read-once oblivious arithmetic branching programs. Zbl 1378.68080
Gurjar, Rohit; Korwar, Arpita; Saxena, Nitin
2017
Locally checkable proofs in distributed computing. Zbl 1401.68085
Göös, Mika; Suomela, Jukka
2016
Anti-concentration for polynomials of independent random variables. Zbl 1392.68193
Meka, Raghu; Nguyen, Oanh; Vu, Van
2016
A tradeoff between length and width in resolution. Zbl 1355.03047
Thapen, Neil
2016
Interactive proofs for $$\mathsf{BQP}$$ via self-tested graph states. Zbl 1362.68087
McKague, Matthew
2016
Lower bounds for non-commutative skew circuits. Zbl 1393.68063
Limaye, Nutan; Malod, Guillaume; Srinivasan, Srikanth
2016
Communication complexity of set-disjointness for all probabilities. Zbl 1365.68259
Göös, Mika; Watson, Thomas
2016
Lattice sparsification and the approximate closest vector problem. Zbl 1362.68291
2016
Dual polynomials for collision and element distinctness. Zbl 1393.68055
Bun, Mark; Thaler, Justin
2016
Efficient indexing of necklaces and irreducible polynomials over finite fields. Zbl 1373.11080
Kopparty, Swastik; Kumar, Mrinal; Saks, Michael
2016
Simple proof of hardness of feedback vertex set. Zbl 1343.68095
Guruswami, Venkatesan; Lee, Euiwoong
2016
Private learning and sanitization: pure vs. approximate differential privacy. Zbl 1362.68096
Beimel, Amos; Nissim, Kobbi; Stemmer, Uri
2016
Lowest-degree $$k$$-spanner: approximation and hardness. Zbl 1393.68187
Chlamtáč, Eden; Dinitz, Michael
2016
Upper bounds on quantum query complexity inspired by the Elitzur-Vaidman bomb tester. Zbl 1353.81035
Lin, Cedric Yen-Yu; Lin, Han-Hsuan
2016
Dichotomies in equilibrium computation and membership of PLC markets in FIXP. Zbl 1415.91191
Garg, Jugal; Mehta, Ruta; Vazirani, Vijay V.
2016
Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion. Zbl 1393.68190
Louis, Anand; Makarychev, Yury
2016
Minimizing maximum flow-time on related machines. Zbl 1391.90239
Bansal, Nikhil; Cloostermans, Bouke
2016
Robust lower bounds for communication and stream computation. Zbl 1392.68191
Chakrabarti, Amit; Cormode, Graham; Mcgregor, Andrew
2016
Maximizing the spread of influence through a social network. Zbl 1337.91069
Kempe, David; Kleinberg, Jon; Tardos, Éva
2015
New lower bounds for the border rank of matrix multiplication. Zbl 1336.68102
Landsberg, Joseph M.; Ottaviani, Giorgio
2015
The projection games conjecture and the NP-hardness of $$\ln n$$-approximating Set-Cover. Zbl 1335.68097
Moshkovitz, Dana
2015
How hard is it to approximate the Jones polynomial? Zbl 1337.68109
Kuperberg, Greg
2015
Computing the partition function for cliques in a graph. Zbl 1351.05212
Barvinok, Alexander
2015
List-decoding multiplicity codes. Zbl 1397.94127
Kopparty, Swastik
2015
Conditional random fields, planted constraint satisfaction, and entropy concentration. Zbl 1351.68190
Abbe, Emmanuel; Montanari, Andrea
2015
Non-commutative arithmetic circuits with division. Zbl 1403.94130
Hrubeš, Pavel; Wigderson, Avi
2015
The complexity of parity graph homomorphism: an initial investigation. Zbl 1336.68122
Faben, John; Jerrum, Mark
2015
Quantum interactive proofs and the complexity of separability testing. Zbl 1336.68082
Gutoski, Gus; Hayden, Patrick; Milner, Kevin; Wilde, Mark M.
2015
Adapt or die: polynomial lower bounds for non-adaptive dynamic data structures. Zbl 1351.68084
Brody, Joshua; Larsen, Kasper Green
2015
On some extensions of the FKN theorem. Zbl 1352.60029
Jendrej, Jacek; Oleszkiewicz, Krzysztof; Wojtaszczyk, Jakub O.
2015
Quantum algorithm for monotonicity testing on the hypercube. Zbl 1351.68105
Belovs, Aleksandrs; Blais, Eric
2015
On the NP-hardness of approximating ordering-constraint satisfaction problems. Zbl 1335.68094
Austrin, Per; Manokaran, Rajsekar; Wenner, Cenny
2015
A new regularity lemma and faster approximation algorithms for low threshold rank graphs. Zbl 1337.68295
Oveis Gharan, Shayan; Trevisan, Luca
2015
The complexity of deciding statistical properties of samplable distributions. Zbl 1336.68108
Watson, Thomas
2015
Matchgates revisited. Zbl 1342.68156
Cai, Jin-Yi; Gorenstein, Aaron
2014
Grothendieck inequalities for semidefinite programs with rank constraint. Zbl 1297.68261
Briët, Jop; de Oliveira Filho, Fernando Mário; Vallentin, Frank
2014
The need for structure in quantum speedups. Zbl 1298.81045
Aaronson, Scott; Ambainis, Andris
2014
An optimal lower bound for monotonicity testing over hypergrids. Zbl 1319.68098
2014
A regularity lemma and low-weight approximators for low-degree polynomial threshold functions. Zbl 1366.68089
Diakonikolas, Ilias; Servedio, Rocco A.; Tan, Li-Yang; Wan, Andrew
2014
Bounding the sensitivity of polynomial threshold functions. Zbl 1366.68096
2014
Width-parametrized SAT: time-space tradeoffs. Zbl 1319.68094
Allender, Eric; Chen, Shiteng; Lou, Tiancheng; Papakonstantinou, Periklis A.; Tang, Bangsheng
2014
Lower bounds for the average and smoothed number of Pareto-optima. Zbl 1354.90126
Brunsch, Tobias; Goyal, Navin; Rademacher, Luis; Röglin, Heiko
2014
Learning $$k$$-modal distributions via testing. Zbl 1319.68119
Daskalakis, Constantinos; Diakonikolas, Ilias; Servedio, Rocco A.
2014
On reconstruction and testing of read-once formulas. Zbl 1319.68113
Shpilka, Amir; Volkovich, Ilya
2014
Approximation algorithm for non-Boolean Max-$$k$$-CSP. Zbl 1319.68254
Makarychev, Konstantin; Makarychev, Yury
2014
Efficient rounding for the noncommutative Grothendieck inequality. Zbl 1302.68323
Naor, Assaf; Regev, Oded; Vidick, Thomas
2014
Improved inapproximability for TSP. Zbl 1366.68077
Lampis, Michael
2014
Dimension-free $$L_2$$ maximal inequality for spherical means in the hypercube. Zbl 1298.42022
Harrow, Aram W.; Kolla, Alexandra; Schulman, Leonard J.
2014
Tight bounds for monotone switching networks via Fourier analysis. Zbl 1319.68100
Chan, Siu Man; Potechin, Aaron
2014
Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. Zbl 1366.68068
Allender, Eric; Lange, Klaus-Jörn
2014
Approximation resistance on satisfiable instances for predicates with few accepting inputs. Zbl 1319.68111
Huang, Sangxia
2014
The computational complexity of linear optics. Zbl 1298.81046
Aaronson, Scott; Arkhipov, Alex
2013
Inapproximability of NP-complete variants of Nash equilibrium. Zbl 1366.68071
Austrin, Per; Braverman, Mark; Chlamtáč, Eden
2013
Making polynomials robust to noise. Zbl 1366.68063
Sherstov, Alexander A.
2013
Approximating the AND-OR tree. Zbl 1328.68078
Sherstov, Alexander A.
2013
The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Zbl 1366.68073
Gottesman, Daniel; Irani, Sandy
2013
Pseudorandomness for width-2 branching programs. Zbl 1300.68037
Bogdanov, Andrej; Dvir, Zeev; Verbin, Elad; Yehudayoff, Amir
2013
Circumventing $$d$$-to-$$1$$ for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Zbl 1366.68084
Wenner, Cenny
2013
Hardness of vertex deletion and project scheduling. Zbl 1366.68083
Svensson, Ola
2013
The power of nondeterminism in self-assembly. Zbl 1366.68054
Bryans, Nathaniel; Chiniforooshan, Ehsan; Doty, David; Kari, Lila; Seki, Shinnosuke
2013
The complexity of the fermionant and immanants of constant width. Zbl 1366.68078
Mertens, Stephan; Moore, Cristopher
2013
Almost $$k$$-wise vs. $$k$$-wise independent permutations, and uniformity for general group actions. Zbl 1297.68183
Alon, Noga; Lovett, Shachar
2013
...and 109 more Documents
all top 5

### Cited by 2,650 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 D’Angelo, Gianlorenzo 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 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,550 more Authors
all top 5

### Cited in 256 Journals

 95 Theoretical Computer Science 93 SIAM Journal on Computing 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 The Journal of Artificial Intelligence Research (JAIR) 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 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

 940 Computer science (68-XX) 355 Combinatorics (05-XX) 291 Operations research, mathematical programming (90-XX) 218 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 191 Quantum theory (81-XX) 133 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 Real functions (26-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 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)