×

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

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

Publications by Year

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

Citations by Year