×

zbMATH — the first resource for mathematics

ACM Transactions on Computation Theory

Short Title: ACM Trans. Comput. Theory
Publisher: Association for Computing Machinery (ACM), New York, NY
ISSN: 1942-3454; 1942-3462/e
Online: https://dl.acm.org/loi/toct
Comments: Indexed cover-to-cover
Documents Indexed: 168 Publications (since 2009)
References Indexed: 37 Publications with 947 References.
all top 5

Authors

7 Pilipczuk, Michał
6 Viola, Emanuele
5 Goldberg, Leslie Ann
5 Pilipczuk, Marcin L.
5 Pitassi, Toniann
5 Ron, Dana
4 Cook, Stephen Arthur
4 Fellows, Michael Ralph
4 Jerrum, Mark R.
4 Mahajan, Meena
4 O’Donnell, Ryan
4 Sarma M. N., Jayalal
4 Saurabh, Saket
3 Beame, Paul W.
3 Beyersdorff, Olaf
3 Chen, Hubie
3 Cygan, Marek
3 Filmus, Yuval
3 Goldreich, Oded
3 Håstad, Johan Torkel
3 Hitchcock, John M.
3 Kerenidis, Iordanis
3 Kratsch, Stefan
3 Limaye, Nutan
3 Lokshtanov, Daniel
3 Razborov, Aleksandr Aleksandrovich
3 Sreenivasaiah, Karteek
3 Wahlström, Magnus
3 Živný, Stanislav
2 Agrawal, Akanksha
2 Allender, Eric W.
2 Arvind, Vikraman
2 Austrin, Per
2 Aydinlioǧlu, Bariş
2 Bach, Eric
2 Blais, Eric
2 Canonne, Clement Louis
2 Chattopadhyay, Arkadev
2 Datta, Samir
2 De, Anindya K.
2 Fomin, Fedor V.
2 Fontes, Lila
2 Fulla, Peter
2 Gál, Anna
2 Ganardi, Moses
2 Göbel, Andreas-Nikolas
2 Gur, Tom
2 Gurjar, Rohit
2 Haviv, Ishay
2 Iwama, Kazuo
2 Jansen, Bart M. P.
2 Kayal, Neeraj
2 Korwar, Arpita
2 Krebs, Andreas
2 Kulkarni, Raghav
2 Lachish, Oded
2 Larose, Benoit
2 Lauria, Massimo
2 Lee, Chin Ho
2 Lohrey, Markus
2 Lutz, Jack H.
2 McKenzie, Pierre
2 Messner, Jochen
2 Mossel, Elchanan
2 Müller, Moritz
2 Pavan, Aduri
2 Raskhodnikova, Sofya
2 Regev, Oded
2 Richerby, David M.
2 Roland, Jérémie
2 Rosamond, Frances A.
2 Saha, Chandan
2 Santhanam, Rahul
2 Schoenebeck, Grant R.
2 Tewari, Raghunath
2 Thierauf, Thomas
2 Torán, Jacobo
2 Tsur, Gilad
2 Vinodchandran, N. Variyam
2 Volkovich, Ilya
2 Wrochna, Marcin
2 Wu, Yi
2 Zhou, Yuan
1 Aaronson, Scott
1 Ada, Anil
1 Adamaszek, Anna
1 Ailon, Nir
1 Ambainis, Andris
1 Artemenko, Sergei
1 Aviv, Nir
1 Awasthi, Pranjal
1 Barber, David G.
1 Ben-Sasson, Eli
1 Bhattacharyya, Arnab
1 Bhattacharyya, Rishiraj
1 Black, Timothy J. F.
1 Bläser, Markus
1 Bliznets, Ivan A.
1 Boczkowski, Lucas
1 Bogdanov, Andrej
...and 201 more Authors

Publications by Year

Citations contained in zbMATH Open

95 Publications have been cited 356 times in 337 Documents Cited by Year
On multiway cut parameterized above lower bounds. Zbl 1322.68098
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
29
2013
Complexity hierarchies beyond elementary. Zbl 1347.68162
Schmitz, Sylvain
19
2016
Algebrization: a new barrier in complexity theory. Zbl 1322.68080
Aaronson, Scott; Wigderson, Avi
18
2009
(Leveled) fully homomorphic encryption without bootstrapping. Zbl 1347.68121
Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod
14
2014
Directed planar reachability is in unambiguous log-space. Zbl 1322.68095
Bourke, Chris; Tewari, Raghunath; Vinodchandran, N. V.
14
2009
The computational complexity of Nash equilibria in concisely represented games. Zbl 1322.68110
Schoenebeck, Grant R.; Vadhan, Salil
12
2012
Optimal lower bounds for locality-sensitive hashing (except when \(q\) is tiny). Zbl 1320.68095
O’Donnell, Ryan; Wu, Yi; Zhou, Yuan
11
2014
Compressed matrix multiplication. Zbl 1322.65055
Pagh, Rasmus
11
2013
Complexity theory for operators in analysis. Zbl 1322.68083
Kawamura, Akitoshi; Cook, Stephen
10
2012
Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099
Dalmau, Víctor; Krokhin, Andrei
10
2013
Exploring the subexponential complexity of completion problems. Zbl 1347.68180
Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve
7
2015
Characterizing arithmetic read-once formulae. Zbl 1347.68148
Volkovich, Ilya
7
2016
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
6
2015
The hardness of being private. Zbl 1321.94032
Ada, Anil; Chattopadhyay, Arkadev; Cook, Stephen A.; Fontes, Lila; Koucký, Michal; Pitassi, Toniann
6
2014
A simple proof of Bazzi’s theorem. Zbl 1322.68108
Razborov, Alexander
6
2009
A complexity dichotomy for finding disjoint solutions of vertex deletion problems. Zbl 1322.68101
Fellows, Michael R.; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf
6
2011
Exact quantum algorithms for the leader election problem. Zbl 1322.68077
Tani, Seiichiro; Kobayashi, Hirotada; Matsumoto, Keiji
6
2012
On the one-way function candidate proposed by Goldreich. Zbl 1347.94029
Cook, James; Etesami, Omid; Miller, Rachel; Trevisan, Luca
5
2014
Some hard families of parameterized counting problems. Zbl 1348.68066
Jerrum, Mark; Meeks, Kitty
5
2015
Mutual dimension. Zbl 1348.03041
Case, Adam; Lutz, Jack H.
5
2015
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
5
2014
Algorithmic information, plane Kakeya sets, and conditional dimension. Zbl 1427.68132
Lutz, Jack H.; Lutz, Neil
4
2018
New insights on the (non-)hardness of circuit minimization and related problems. Zbl 1441.68081
Allender, Eric; Hirahara, Shuichi
4
2019
Optimal sparsification for some binary CSPs using low-degree polynomials. Zbl 07143744
Jansen, Bart M. P.; Pieterse, Astrid
4
2019
The complexity of the nucleolus in compact games. Zbl 1348.91073
Greco, Gianluigi; Malizia, Enrico; Palopoli, Luigi; Scarcello, Francesco
4
2014
Collusion-resistant mechanisms with verification yielding optimal solutions. Zbl 1322.68255
Penna, Paolo; Ventre, Carmine
4
2012
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
4
2012
Distortion is fixed parameter tractable. Zbl 1322.68102
Fellows, Michael; Fomin, Fedor V.; Lokshtanov, Daniel; Losievskaja, Elena; Rosamond, Frances; Saurabh, Saket
4
2013
Real advantage. Zbl 1322.68076
Razborov, Alexander; Viola, Emanuele
4
2013
On sample-based testers. Zbl 1427.68360
Goldreich, Oded; Ron, Dana
3
2016
Finding consensus strings with small length difference between input and solution strings. Zbl 1427.68131
Schmid, Markus L.
3
2017
On space efficiency of algorithms working on structural decompositions of graphs. Zbl 1427.68130
Pilipczuk, Michał; Wrochna, Marcin
3
2017
On minrank and forbidden subgraphs. Zbl 07143736
Haviv, Ishay
3
2019
FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders. Zbl 1347.68167
Fellows, Michael R.; Jansen, Bart M. P.
3
2014
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
3
2014
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
Improved separations between nondeterministic and randomized multiparty communication. Zbl 1322.68074
David, Matei; Pitassi, Toniann; Viola, Emanuele
3
2009
Sound 3-query PCPPs are long. Zbl 1322.68094
Ben-Sasson, Eli; Harsha, Prahladh; Lachish, Oded; Matsliah, Arie
3
2009
Formula caching in DPLL. Zbl 1322.68175
Beame, Paul; Impagliazzo, Russell; Pitassi, Toniann; Segerlind, Nathan
3
2010
Planarity, determinants, permanents, and (unique) matchings. Zbl 1322.05088
Datta, Samir; Kulkarni, Raghav; Limaye, Nutan; Mahajan, Meena
3
2010
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity. Zbl 1322.68109
Ron, Dana; Rubinfeld, Ronitt; Safra, Muli; Samorodnitsky, Alex; Weinstein, Omri
3
2012
Quantum rejection sampling. Zbl 1322.68079
Ozols, Maris; Roetteler, Martin; Roland, Jérémie
3
2013
Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
2
2016
Randomized communication versus partition number. Zbl 1427.68083
Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas
2
2018
Tight running time lower bounds for vertex deletion problems. Zbl 1427.68245
Komusiewicz, Christian
2
2018
Directed multicut is W[1]-hard, even for four terminal pairs. Zbl 1427.68252
Pilipczuk, Marcin; Wahlström, Magnus
2
2018
Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits. Zbl 1427.68111
Artemenko, Sergei; Shaltiel, Ronen
2
2017
Asking the metaquestions in constraint tractability. Zbl 1427.68115
Chen, Hubie; Larose, Benoit
2
2017
Distribution testing lower bounds via reductions from communication complexity. Zbl 1440.68323
Blais, Eric; Canonne, Clément L.; Gur, Tom
2
2019
Simultaneous feedback vertex set: a parameterized perspective. Zbl 07143721
Agrawal, Akanksha; Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket
2
2018
The complexity of Boolean surjective general-valued CSPs. Zbl 1441.68091
Fulla, Peter; Uppman, Hannes; Živný, Stanislav
2
2019
New resolution-based QBF calculi and their proof complexity. Zbl 07143742
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
2
2019
Evolvability of real functions. Zbl 1347.68314
Valiant, Paul
2
2014
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1347.68171
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2014
Using parametric transformations toward polynomial kernels for packing problems allowing overlaps. Zbl 1347.68353
Fernau, Henning; López-Ortiz, Alejandro; Romero, Jazmín
2
2015
Logspace reduction of directed reachability for bounded genus graphs to the planar case. Zbl 1322.68107
Kynčl, Jan; Vyskočil, Tomáš
2
2010
Tradeoffs and average-case equilibria in selfish routing. Zbl 1322.68021
Hoefer, Martin; Souza, Alexander
2
2010
Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\). Zbl 1322.68092
Arvind, Vikraman; Torán, Jacobo
2
2011
Three-query locally decodable codes with higher correctness require exponential length. Zbl 1322.94110
Gal, Anna; Mills, Andrew
2
2012
On the sum of square roots of polynomials and related problems. Zbl 1322.68104
Kayal, Neeraj; Saha, Chandan
2
2012
On the usefulness of predicates. Zbl 1322.68093
Austrin, Per; Håstad, Johan
2
2013
High-confidence predictions under adversarial uncertainty. Zbl 1322.68266
Drucker, Andrew
2
2013
Space-efficient approximations for subset sum. Zbl 1427.68367
Gál, Anna; Jang, Jing-Tang; Limaye, Nutan; Mahajan, Meena; Sreenivasaiah, Karteek
1
2016
Quadratic maps are hard to sample. Zbl 1427.68109
Viola, Emanuele
1
2016
Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs. Zbl 1427.68077
Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir; Volk, Ben Lee
1
2018
Invariance principle on the slice. Zbl 1427.60018
Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl
1
2018
The coin problem for product tests. Zbl 1427.68220
Lee, Chin Ho; Viola, Emanuele
1
2018
Lower bounds for constant query affine-invariant LCCs and LTCs. Zbl 1427.94088
Bhattacharyya, Arnab; Gopi, Sivakanth
1
2017
Exact perfect matching in complete graphs. Zbl 1427.68243
Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Thierauf, Thomas
1
2017
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
1
2017
Hardness of approximation for strip packing. Zbl 1427.68100
Adamaszek, Anna; Kociumaka, Tomasz; Pilipczuk, Marcin; Pilipczuk, Michał
1
2017
Proof complexity modulo the polynomial hierarchy: understanding alternation as a source of hardness. Zbl 1427.03063
Chen, Hubie
1
2017
Metric 1-median selection: query complexity vs. approximation ratio. Zbl 1427.68114
Chang, Ching-Lueh
1
2017
Lower bounds for sum and sum of products of Read-once formulas. Zbl 07143716
Ramya, C.; Rao, B. V. Raghavendra
1
2019
Reconstruction of full rank algebraic branching programs. Zbl 1440.68080
Kayal, Neeraj; Nair, Vineet; Saha, Chandan; Tavenas, Sébastien
1
2019
Strong locally testable codes with relaxed local decoders. Zbl 07143733
Goldreich, Oded; Gur, Tom; Komargodski, Ilan
1
2019
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
1
2019
On approximate decidability of minimal programs. Zbl 1347.68096
Teutsch, Jason; Zimand, Marius
1
2015
An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model. Zbl 1347.68163
Ailon, Nir
1
2016
The complexity of the comparator circuit value problem. Zbl 1347.68156
Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man
1
2014
Advice lower bounds for the dense model theorem. Zbl 1347.68174
Watson, Thomas
1
2014
Smoothed complexity theory. Zbl 1347.68155
Bläser, Markus; Manthey, Bodo
1
2015
The fine classification of conjunctive queries and parameterized logarithmic space. Zbl 1347.68179
Chen, Hubie; Müller, Moritz
1
2015
Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups. Zbl 1347.68173
O’Donnell, Ryan; Wu, Yi; Zhou, Yuan
1
2015
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. Zbl 1321.68309
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
1
2014
Cell-probe proofs. Zbl 1322.68064
Yin, Yitong
1
2010
Lower bounds for coin-weighing problems. Zbl 1322.68090
Purdy, Eric
1
2011
Kolmogorov complexity in randomness extraction. Zbl 1322.68114
Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V.
1
2011
The value of multiple read/write streams for approximating frequency moments. Zbl 1322.68072
Beame, Paul; Huynh, Trinh
1
2012
Approximating linear threshold predicates. Zbl 1322.68097
Cheraghchi, Mahdi; Håstad, Johan; Isaksson, Marcus; Svensson, Ola
1
2012
Extractors and lower bounds for locally samplable sources. Zbl 1322.65009
De, Anindya; Watson, Thomas
1
2012
On the computational complexity of stochastic controller optimization in POMDPs. Zbl 1322.68111
Vlassis, Nikos; Littman, Michael L.; Barber, David
1
2012
Alternation-trading proofs, linear programming, and lower bounds. Zbl 1322.68091
Williams, Ryan
1
2013
On approximating the number of relevant variables in a function. Zbl 1322.68261
Ron, Dana; Tsur, Gilad
1
2013
Exact learning algorithms, betting games, and circuit lower bounds. Zbl 1322.68115
Harkins, Ryan C.; Hitchcock, John M.
1
2013
New insights on the (non-)hardness of circuit minimization and related problems. Zbl 1441.68081
Allender, Eric; Hirahara, Shuichi
4
2019
Optimal sparsification for some binary CSPs using low-degree polynomials. Zbl 07143744
Jansen, Bart M. P.; Pieterse, Astrid
4
2019
On minrank and forbidden subgraphs. Zbl 07143736
Haviv, Ishay
3
2019
Distribution testing lower bounds via reductions from communication complexity. Zbl 1440.68323
Blais, Eric; Canonne, Clément L.; Gur, Tom
2
2019
The complexity of Boolean surjective general-valued CSPs. Zbl 1441.68091
Fulla, Peter; Uppman, Hannes; Živný, Stanislav
2
2019
New resolution-based QBF calculi and their proof complexity. Zbl 07143742
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
2
2019
Lower bounds for sum and sum of products of Read-once formulas. Zbl 07143716
Ramya, C.; Rao, B. V. Raghavendra
1
2019
Reconstruction of full rank algebraic branching programs. Zbl 1440.68080
Kayal, Neeraj; Nair, Vineet; Saha, Chandan; Tavenas, Sébastien
1
2019
Strong locally testable codes with relaxed local decoders. Zbl 07143733
Goldreich, Oded; Gur, Tom; Komargodski, Ilan
1
2019
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
1
2019
Algorithmic information, plane Kakeya sets, and conditional dimension. Zbl 1427.68132
Lutz, Jack H.; Lutz, Neil
4
2018
Randomized communication versus partition number. Zbl 1427.68083
Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas
2
2018
Tight running time lower bounds for vertex deletion problems. Zbl 1427.68245
Komusiewicz, Christian
2
2018
Directed multicut is W[1]-hard, even for four terminal pairs. Zbl 1427.68252
Pilipczuk, Marcin; Wahlström, Magnus
2
2018
Simultaneous feedback vertex set: a parameterized perspective. Zbl 07143721
Agrawal, Akanksha; Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket
2
2018
Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs. Zbl 1427.68077
Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir; Volk, Ben Lee
1
2018
Invariance principle on the slice. Zbl 1427.60018
Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl
1
2018
The coin problem for product tests. Zbl 1427.68220
Lee, Chin Ho; Viola, Emanuele
1
2018
Finding consensus strings with small length difference between input and solution strings. Zbl 1427.68131
Schmid, Markus L.
3
2017
On space efficiency of algorithms working on structural decompositions of graphs. Zbl 1427.68130
Pilipczuk, Michał; Wrochna, Marcin
3
2017
Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits. Zbl 1427.68111
Artemenko, Sergei; Shaltiel, Ronen
2
2017
Asking the metaquestions in constraint tractability. Zbl 1427.68115
Chen, Hubie; Larose, Benoit
2
2017
Lower bounds for constant query affine-invariant LCCs and LTCs. Zbl 1427.94088
Bhattacharyya, Arnab; Gopi, Sivakanth
1
2017
Exact perfect matching in complete graphs. Zbl 1427.68243
Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Thierauf, Thomas
1
2017
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
1
2017
Hardness of approximation for strip packing. Zbl 1427.68100
Adamaszek, Anna; Kociumaka, Tomasz; Pilipczuk, Marcin; Pilipczuk, Michał
1
2017
Proof complexity modulo the polynomial hierarchy: understanding alternation as a source of hardness. Zbl 1427.03063
Chen, Hubie
1
2017
Metric 1-median selection: query complexity vs. approximation ratio. Zbl 1427.68114
Chang, Ching-Lueh
1
2017
Complexity hierarchies beyond elementary. Zbl 1347.68162
Schmitz, Sylvain
19
2016
Characterizing arithmetic read-once formulae. Zbl 1347.68148
Volkovich, Ilya
7
2016
On sample-based testers. Zbl 1427.68360
Goldreich, Oded; Ron, Dana
3
2016
Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
2
2016
Space-efficient approximations for subset sum. Zbl 1427.68367
Gál, Anna; Jang, Jing-Tang; Limaye, Nutan; Mahajan, Meena; Sreenivasaiah, Karteek
1
2016
Quadratic maps are hard to sample. Zbl 1427.68109
Viola, Emanuele
1
2016
An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model. Zbl 1347.68163
Ailon, Nir
1
2016
Exploring the subexponential complexity of completion problems. Zbl 1347.68180
Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve
7
2015
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
6
2015
Some hard families of parameterized counting problems. Zbl 1348.68066
Jerrum, Mark; Meeks, Kitty
5
2015
Mutual dimension. Zbl 1348.03041
Case, Adam; Lutz, Jack H.
5
2015
Using parametric transformations toward polynomial kernels for packing problems allowing overlaps. Zbl 1347.68353
Fernau, Henning; López-Ortiz, Alejandro; Romero, Jazmín
2
2015
On approximate decidability of minimal programs. Zbl 1347.68096
Teutsch, Jason; Zimand, Marius
1
2015
Smoothed complexity theory. Zbl 1347.68155
Bläser, Markus; Manthey, Bodo
1
2015
The fine classification of conjunctive queries and parameterized logarithmic space. Zbl 1347.68179
Chen, Hubie; Müller, Moritz
1
2015
Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups. Zbl 1347.68173
O’Donnell, Ryan; Wu, Yi; Zhou, Yuan
1
2015
(Leveled) fully homomorphic encryption without bootstrapping. Zbl 1347.68121
Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod
14
2014
Optimal lower bounds for locality-sensitive hashing (except when \(q\) is tiny). Zbl 1320.68095
O’Donnell, Ryan; Wu, Yi; Zhou, Yuan
11
2014
The hardness of being private. Zbl 1321.94032
Ada, Anil; Chattopadhyay, Arkadev; Cook, Stephen A.; Fontes, Lila; Koucký, Michal; Pitassi, Toniann
6
2014
On the one-way function candidate proposed by Goldreich. Zbl 1347.94029
Cook, James; Etesami, Omid; Miller, Rachel; Trevisan, Luca
5
2014
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
5
2014
The complexity of the nucleolus in compact games. Zbl 1348.91073
Greco, Gianluigi; Malizia, Enrico; Palopoli, Luigi; Scarcello, Francesco
4
2014
FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders. Zbl 1347.68167
Fellows, Michael R.; Jansen, Bart M. P.
3
2014
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
3
2014
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
Evolvability of real functions. Zbl 1347.68314
Valiant, Paul
2
2014
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1347.68171
Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh
2
2014
The complexity of the comparator circuit value problem. Zbl 1347.68156
Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man
1
2014
Advice lower bounds for the dense model theorem. Zbl 1347.68174
Watson, Thomas
1
2014
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. Zbl 1321.68309
Etessami, Kousha; Stewart, Alistair; Yannakakis, Mihalis
1
2014
On multiway cut parameterized above lower bounds. Zbl 1322.68098
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
29
2013
Compressed matrix multiplication. Zbl 1322.65055
Pagh, Rasmus
11
2013
Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099
Dalmau, Víctor; Krokhin, Andrei
10
2013
Distortion is fixed parameter tractable. Zbl 1322.68102
Fellows, Michael; Fomin, Fedor V.; Lokshtanov, Daniel; Losievskaja, Elena; Rosamond, Frances; Saurabh, Saket
4
2013
Real advantage. Zbl 1322.68076
Razborov, Alexander; Viola, Emanuele
4
2013
Quantum rejection sampling. Zbl 1322.68079
Ozols, Maris; Roetteler, Martin; Roland, Jérémie
3
2013
On the usefulness of predicates. Zbl 1322.68093
Austrin, Per; Håstad, Johan
2
2013
High-confidence predictions under adversarial uncertainty. Zbl 1322.68266
Drucker, Andrew
2
2013
Alternation-trading proofs, linear programming, and lower bounds. Zbl 1322.68091
Williams, Ryan
1
2013
On approximating the number of relevant variables in a function. Zbl 1322.68261
Ron, Dana; Tsur, Gilad
1
2013
Exact learning algorithms, betting games, and circuit lower bounds. Zbl 1322.68115
Harkins, Ryan C.; Hitchcock, John M.
1
2013
The computational complexity of Nash equilibria in concisely represented games. Zbl 1322.68110
Schoenebeck, Grant R.; Vadhan, Salil
12
2012
Complexity theory for operators in analysis. Zbl 1322.68083
Kawamura, Akitoshi; Cook, Stephen
10
2012
Exact quantum algorithms for the leader election problem. Zbl 1322.68077
Tani, Seiichiro; Kobayashi, Hirotada; Matsumoto, Keiji
6
2012
Collusion-resistant mechanisms with verification yielding optimal solutions. Zbl 1322.68255
Penna, Paolo; Ventre, Carmine
4
2012
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
4
2012
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity. Zbl 1322.68109
Ron, Dana; Rubinfeld, Ronitt; Safra, Muli; Samorodnitsky, Alex; Weinstein, Omri
3
2012
Three-query locally decodable codes with higher correctness require exponential length. Zbl 1322.94110
Gal, Anna; Mills, Andrew
2
2012
On the sum of square roots of polynomials and related problems. Zbl 1322.68104
Kayal, Neeraj; Saha, Chandan
2
2012
The value of multiple read/write streams for approximating frequency moments. Zbl 1322.68072
Beame, Paul; Huynh, Trinh
1
2012
Approximating linear threshold predicates. Zbl 1322.68097
Cheraghchi, Mahdi; Håstad, Johan; Isaksson, Marcus; Svensson, Ola
1
2012
Extractors and lower bounds for locally samplable sources. Zbl 1322.65009
De, Anindya; Watson, Thomas
1
2012
On the computational complexity of stochastic controller optimization in POMDPs. Zbl 1322.68111
Vlassis, Nikos; Littman, Michael L.; Barber, David
1
2012
A complexity dichotomy for finding disjoint solutions of vertex deletion problems. Zbl 1322.68101
Fellows, Michael R.; Guo, Jiong; Moser, Hannes; Niedermeier, Rolf
6
2011
Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\). Zbl 1322.68092
Arvind, Vikraman; Torán, Jacobo
2
2011
Lower bounds for coin-weighing problems. Zbl 1322.68090
Purdy, Eric
1
2011
Kolmogorov complexity in randomness extraction. Zbl 1322.68114
Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V.
1
2011
Formula caching in DPLL. Zbl 1322.68175
Beame, Paul; Impagliazzo, Russell; Pitassi, Toniann; Segerlind, Nathan
3
2010
Planarity, determinants, permanents, and (unique) matchings. Zbl 1322.05088
Datta, Samir; Kulkarni, Raghav; Limaye, Nutan; Mahajan, Meena
3
2010
Logspace reduction of directed reachability for bounded genus graphs to the planar case. Zbl 1322.68107
Kynčl, Jan; Vyskočil, Tomáš
2
2010
Tradeoffs and average-case equilibria in selfish routing. Zbl 1322.68021
Hoefer, Martin; Souza, Alexander
2
2010
Cell-probe proofs. Zbl 1322.68064
Yin, Yitong
1
2010
Algebrization: a new barrier in complexity theory. Zbl 1322.68080
Aaronson, Scott; Wigderson, Avi
18
2009
Directed planar reachability is in unambiguous log-space. Zbl 1322.68095
Bourke, Chris; Tewari, Raghunath; Vinodchandran, N. V.
14
2009
A simple proof of Bazzi’s theorem. Zbl 1322.68108
Razborov, Alexander
6
2009
Improved separations between nondeterministic and randomized multiparty communication. Zbl 1322.68074
David, Matei; Pitassi, Toniann; Viola, Emanuele
3
2009
Sound 3-query PCPPs are long. Zbl 1322.68094
Ben-Sasson, Eli; Harsha, Prahladh; Lachish, Oded; Matsliah, Arie
3
2009
all top 5

Cited by 609 Authors

10 Pilipczuk, Marcin L.
8 Pilipczuk, Michał
7 Saurabh, Saket
6 Gur, Tom
6 Jansen, Bart M. P.
5 Applebaum, Benny
5 Lutz, Neil
5 Marx, Dániel
5 Pieterse, Astrid
5 Steinberg, Florian
5 Vinodchandran, N. Variyam
5 Živný, Stanislav
4 Allender, Eric W.
4 Chen, Hubie
4 Chitnis, Rajesh Hemant
4 Cygan, Marek
4 Datta, Samir
4 Fluschnik, Till
4 Kawamura, Akitoshi
4 Lazić, Ranko
4 Lokshtanov, Daniel
4 Raghavendra Rao, B. V.
4 Schmitz, Sylvain
4 Stull, Donald M.
4 Tewari, Raghunath
4 Tu, Jianhua
4 Van Leeuwen, Erik Jan
4 Viola, Emanuele
4 Woodruff, David P.
3 Altman, Harry J.
3 Beyersdorff, Olaf
3 Blinkhorn, Joshua
3 Brandt, Felix
3 Fischer, Felix
3 Goldberg, Leslie Ann
3 Göös, Mika
3 Greco, Gianluigi
3 Guruswami, Venkatesan
3 Hermelin, Danny
3 Iwata, Yoichi
3 Komusiewicz, Christian
3 Kozik, Marcin
3 Kratsch, Stefan
3 Krokhin, Andrei A.
3 Lauria, Massimo
3 Li, Shaohua
3 Lovett, Shachar
3 Mahajan, Meena
3 Mnich, Matthias
3 Molter, Hendrik
3 Niedermeier, Rolf
3 Palazuelos, Carlos
3 Ramanujan, M. S.
3 Roth, Marc
3 Rothblum, Ron D.
3 Sarma M. N., Jayalal
3 Sunil, K. S.
3 Thaler, Justin
3 Thapper, Johan
3 Thierauf, Thomas
3 van Bevern, René
3 Wahlström, Magnus
3 Weinstein, Omri
3 Zehavi, Meirav
3 Ziegler, Martin
2 Agrawal, Akanksha
2 Balla, Igor
2 Birmele, Etienne
2 Bulteau, Laurent
2 Canteaut, Anne
2 Carpov, Sergiu
2 Chakrabarti, Amit
2 Chen, Jian-er
2 Chen, Xi
2 Dalmau, Víctor
2 de Montgolfier, Fabien
2 Downey, Rodney Graham
2 Drange, Pål Grønås
2 Engels, Christian
2 Finkel, Alain
2 Fontaine, Caroline
2 Froese, Vincent
2 Gabarró, Joaquim
2 Garg, Ankit
2 Göbel, Andreas-Nikolas
2 Gurjar, Rohit
2 Hajiaghayi, Mohammad Taghi
2 Holzer, Markus
2 Ianovski, Egor
2 Ishai, Yuval
2 Jančar, Petr
2 Katoen, Joost-Pieter
2 Kerenidis, Iordanis
2 Koiran, Pascal
2 Kosowski, Adrian
2 Krysta, Piotr
2 Kulkarni, Raghav
2 Kwan, Matthew
2 Lepoint, Tancrède
2 Leroux, Jérôme
...and 509 more Authors
all top 5

Cited in 76 Journals

34 SIAM Journal on Computing
24 Algorithmica
23 Theoretical Computer Science
18 Journal of Computer and System Sciences
18 Theory of Computing Systems
17 Computational Complexity
11 SIAM Journal on Discrete Mathematics
7 Information and Computation
6 Artificial Intelligence
6 Information Processing Letters
5 Journal of Cryptology
5 Logical Methods in Computer Science
4 Discrete Applied Mathematics
4 SIAM Journal on Matrix Analysis and Applications
3 Israel Journal of Mathematics
3 Cybernetics and Systems Analysis
3 Journal of Machine Learning Research (JMLR)
3 ACM Transactions on Computational Logic
2 Discrete Mathematics
2 Mathematical Proceedings of the Cambridge Philosophical Society
2 Information Sciences
2 The Journal of Symbolic Logic
2 Combinatorica
2 Annals of Pure and Applied Logic
2 Discrete & Computational Geometry
2 Journal of Automated Reasoning
2 MSCS. Mathematical Structures in Computer Science
2 International Journal of Foundations of Computer Science
2 Journal of Discrete Algorithms
2 Discrete Analysis
1 Acta Informatica
1 Communications in Mathematical Physics
1 International Journal of Theoretical Physics
1 Journal of Mathematical Physics
1 The Annals of Statistics
1 Applied Mathematics and Computation
1 Journal of Algebra
1 Journal of Combinatorial Theory. Series B
1 Mathematics of Operations Research
1 Transactions of the American Mathematical Society
1 European Journal of Combinatorics
1 Operations Research Letters
1 Journal of Symbolic Computation
1 Journal of Complexity
1 Journal of Computer Science and Technology
1 Journal of the American Mathematical Society
1 Formal Aspects of Computing
1 International Journal of Algebra and Computation
1 Games and Economic Behavior
1 Mathematical Programming. Series A. Series B
1 New Zealand Journal of Mathematics
1 Journal of Applied Non-Classical Logics
1 Economic Theory
1 The Electronic Journal of Combinatorics
1 Advances in Computational Mathematics
1 Complexity
1 Discussiones Mathematicae. Graph Theory
1 Soft Computing
1 Journal of Combinatorial Optimization
1 Journal of Scheduling
1 Journal of the ACM
1 Lobachevskii Journal of Mathematics
1 Integers
1 Quantum Information Processing
1 ACM Journal of Experimental Algorithmics
1 Discrete Optimization
1 Science in China. Series F
1 Optimization Letters
1 Journal of Mathematical Cryptology
1 Information and Inference
1 Moscow Journal of Combinatorics and Number Theory
1 Forum of Mathematics, Pi
1 Computability
1 ACM Transactions on Computation Theory
1 Prikladnaya Diskretnaya Matematika
1 Advances in Combinatorics

Citations by Year