×

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: 207 Publications (since 2009)
References Indexed: 37 Publications with 947 References.
all top 5

Authors

8 Saurabh, Saket
8 Viola, Emanuele
7 Goldberg, Leslie Ann
7 Pilipczuk, Michał
7 Ron, Dana
6 Lokshtanov, Daniel
5 Pilipczuk, Marcin L.
5 Pitassi, Toniann
4 Cook, Stephen Arthur
4 Fellows, Michael Ralph
4 Fomin, Fedor V.
4 Goldreich, Oded
4 Hitchcock, John M.
4 Jerrum, Mark R.
4 Limaye, Nutan
4 Mahajan, Meena
4 O’Donnell, Ryan
4 Sarma M. N., Jayalal
4 Wahlström, Magnus
4 Zehavi, Meirav
4 Živný, Stanislav
3 Beame, Paul W.
3 Beyersdorff, Olaf
3 Chen, Hubie
3 Cygan, Marek
3 Filmus, Yuval
3 Galanis, Andreas
3 Göbel, Andreas-Nikolas
3 Håstad, Johan Torkel
3 Kerenidis, Iordanis
3 Kratsch, Stefan
3 Raskhodnikova, Sofya
3 Razborov, Aleksandr Aleksandrovich
3 Sreenivasaiah, Karteek
3 Wrochna, Marcin
2 Agrawal, Akanksha
2 Allender, Eric W.
2 Ambainis, Andris
2 Arvind, Vikraman
2 Austrin, Per
2 Aydinlioǧlu, Bariş
2 Bach, Eric
2 Blais, Eric
2 Cai, Jin-Yi
2 Canonne, Clement Louis
2 Chakraborty, Sourav
2 Chattopadhyay, Arkadev
2 Datta, Samir
2 De, Anindya K.
2 Fontes, Lila
2 Fulla, Peter
2 Gál, Anna
2 Ganardi, Moses
2 Gur, Tom
2 Gurjar, Rohit
2 Haviv, Ishay
2 Iwama, Kazuo
2 Jansen, Bart M. P.
2 Kayal, Neeraj
2 Koroth, Sajin
2 Korwar, Arpita
2 Koucký, Michal
2 Krebs, Andreas
2 Kulkarni, Raghav
2 Lachish, Oded
2 Lagerkvist, Victor
2 Larose, Benoit
2 Lauria, Massimo
2 Lee, Chin Ho
2 Levi, Amit
2 Lohrey, Markus
2 Lutz, Jack H.
2 Lutz, Neil
2 Magniez, Frédéric
2 McKenzie, Pierre
2 Messner, Jochen
2 Mossel, Elchanan
2 Müller, Moritz
2 Niedermeier, Rolf
2 Pallavoor, Ramesh Krishnan S.
2 Panolan, Fahad
2 Pavan, Aduri
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 Srinivasan, Srikanth
2 Tewari, Raghunath
2 Thierauf, Thomas
2 Torán, Jacobo
2 Tsur, Gilad
2 Varma, Nithin M.
2 Vinodchandran, N. Variyam
2 Volkovich, Ilya
2 Wu, Yi
2 Zhou, Yuan
1 Aaronson, Scott
...and 273 more Authors

Publications by Year

Citations contained in zbMATH Open

114 Publications have been cited 491 times in 460 Documents Cited by Year
On multiway cut parameterized above lower bounds. Zbl 1322.68098
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
39
2013
(Leveled) fully homomorphic encryption without bootstrapping. Zbl 1347.68121
Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod
30
2014
Complexity hierarchies beyond elementary. Zbl 1347.68162
Schmitz, Sylvain
27
2016
Algebrization: a new barrier in complexity theory. Zbl 1322.68080
Aaronson, Scott; Wigderson, Avi
20
2009
Directed planar reachability is in unambiguous log-space. Zbl 1322.68095
Bourke, Chris; Tewari, Raghunath; Vinodchandran, N. V.
16
2009
Complexity theory for operators in analysis. Zbl 1322.68083
Kawamura, Akitoshi; Cook, Stephen
14
2012
Compressed matrix multiplication. Zbl 1322.65055
Pagh, Rasmus
13
2013
Optimal lower bounds for locality-sensitive hashing (except when \(q\) is tiny). Zbl 1320.68095
O’Donnell, Ryan; Wu, Yi; Zhou, Yuan
13
2014
The computational complexity of Nash equilibria in concisely represented games. Zbl 1322.68110
Schoenebeck, Grant R.; Vadhan, Salil
12
2012
Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099
Dalmau, Víctor; Krokhin, Andrei
12
2013
Some hard families of parameterized counting problems. Zbl 1348.68066
Jerrum, Mark; Meeks, Kitty
9
2015
Exploring the subexponential complexity of completion problems. Zbl 1347.68180
Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve
8
2015
Characterizing arithmetic read-once formulae. Zbl 1347.68148
Volkovich, Ilya
8
2016
A simple proof of Bazzi’s theorem. Zbl 1322.68108
Razborov, Alexander
8
2009
New resolution-based QBF calculi and their proof complexity. Zbl 07143742
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
7
2019
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
7
2015
On the one-way function candidate proposed by Goldreich. Zbl 1347.94029
Cook, James; Etesami, Omid; Miller, Rachel; Trevisan, Luca
7
2014
Mutual dimension. Zbl 1348.03041
Case, Adam; Lutz, Jack H.
7
2015
Exact quantum algorithms for the leader election problem. Zbl 1322.68077
Tani, Seiichiro; Kobayashi, Hirotada; Matsumoto, Keiji
7
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
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
6
2012
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
6
2014
The hardness of being private. Zbl 1321.94032
Ada, Anil; Chattopadhyay, Arkadev; Cook, Stephen A.; Fontes, Lila; Koucký, Michal; Pitassi, Toniann
6
2014
Algorithmic information, plane Kakeya sets, and conditional dimension. Zbl 1427.68132
Lutz, Jack H.; Lutz, Neil
6
2018
Asking the metaquestions in constraint tractability. Zbl 1427.68115
Chen, Hubie; Larose, Benoit
6
2017
New insights on the (non-)hardness of circuit minimization and related problems. Zbl 1441.68081
Allender, Eric; Hirahara, Shuichi
5
2019
The complexity of the nucleolus in compact games. Zbl 1348.91073
Greco, Gianluigi; Malizia, Enrico; Palopoli, Luigi; Scarcello, Francesco
5
2014
Real advantage. Zbl 1322.68076
Razborov, Alexander; Viola, Emanuele
5
2013
Directed multicut is W[1]-hard, even for four terminal pairs. Zbl 1427.68252
Pilipczuk, Marcin; Wahlström, Magnus
5
2018
Optimal sparsification for some binary CSPs using low-degree polynomials. Zbl 07143744
Jansen, Bart M. P.; Pieterse, Astrid
4
2019
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
4
2014
Sound 3-query PCPPs are long. Zbl 1322.68094
Ben-Sasson, Eli; Harsha, Prahladh; Lachish, Oded; Matsliah, Arie
4
2009
Planarity, determinants, permanents, and (unique) matchings. Zbl 1322.05088
Datta, Samir; Kulkarni, Raghav; Limaye, Nutan; Mahajan, Meena
4
2010
Collusion-resistant mechanisms with verification yielding optimal solutions. Zbl 1322.68255
Penna, Paolo; Ventre, Carmine
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
On sample-based testers. Zbl 1427.68360
Goldreich, Oded; Ron, Dana
4
2016
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
4
2017
On space efficiency of algorithms working on structural decompositions of graphs. Zbl 1427.68130
Pilipczuk, Michał; Wrochna, Marcin
4
2017
The complexity of approximating the matching polynomial in the complex plane. Zbl 07495903
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
3
2021
The complexity of Boolean surjective general-valued CSPs. Zbl 1441.68091
Fulla, Peter; Uppman, Hannes; Živný, Stanislav
3
2019
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 fine classification of conjunctive queries and parameterized logarithmic space. Zbl 1347.68179
Chen, Hubie; Müller, Moritz
3
2015
Improved separations between nondeterministic and randomized multiparty communication. Zbl 1322.68074
David, Matei; Pitassi, Toniann; Viola, Emanuele
3
2009
Logspace reduction of directed reachability for bounded genus graphs to the planar case. Zbl 1322.68107
Kynčl, Jan; Vyskočil, Tomáš
3
2010
Formula caching in DPLL. Zbl 1322.68175
Beame, Paul; Impagliazzo, Russell; Pitassi, Toniann; Segerlind, Nathan
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
On the usefulness of predicates. Zbl 1322.68093
Austrin, Per; Håstad, Johan
3
2013
Quantum rejection sampling. Zbl 1322.68079
Ozols, Maris; Roetteler, Martin; Roland, Jérémie
3
2013
The complexity of approximately counting tree homomorphisms. Zbl 1321.68312
Goldberg, Leslie Ann; Jerrum, Mark
3
2014
Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
3
2016
Tight running time lower bounds for vertex deletion problems. Zbl 1427.68245
Komusiewicz, Christian
3
2018
Invariance principle on the slice. Zbl 1427.60018
Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl
3
2018
Finding consensus strings with small length difference between input and solution strings. Zbl 1427.68131
Schmid, Markus L.
3
2017
Hardness of approximation for strip packing. Zbl 1427.68100
Adamaszek, Anna; Kociumaka, Tomasz; Pilipczuk, Marcin; Pilipczuk, Michał
3
2017
Distribution testing lower bounds via reductions from communication complexity. Zbl 1440.68323
Blais, Eric; Canonne, Clément L.; Gur, Tom
2
2019
Lower bounds for sum and sum of products of read-once formulas. Zbl 1485.68095
Ramya, C.; Raghavendra Rao, B. V.
2
2019
Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. Zbl 1485.68107
Guo, Heng; Lu, Pinyan
2
2018
Simultaneous feedback vertex set: a parameterized perspective. Zbl 1485.68169
Agrawal, Akanksha; Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket
2
2018
Reconstruction of full rank algebraic branching programs. Zbl 1440.68080
Kayal, Neeraj; Nair, Vineet; Saha, Chandan; Tavenas, Sébastien
2
2019
Beyond worst-case (in)approximability of nonsubmodular influence maximization. Zbl 07143728
Schoenebeck, Grant; Tao, Biaoshuai
2
2019
Split contraction: the untold story. Zbl 07143734
Agrawal, Akanksha; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
2
2019
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
2
2019
Evolvability of real functions. Zbl 1347.68314
Valiant, Paul
2
2014
The complexity of the comparator circuit value problem. Zbl 1347.68156
Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man
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
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
High-confidence predictions under adversarial uncertainty. Zbl 1322.68266
Drucker, Andrew
2
2013
A Galois connection for weighted (relational) clones of infinite size. Zbl 1427.68120
Fulla, Peter; Živný, Stanislav
2
2016
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362
Haviv, Ishay; Regev, Oded
2
2016
Space-efficient approximations for subset sum. Zbl 1427.68367
Gál, Anna; Jang, Jing-Tang; Limaye, Nutan; Mahajan, Meena; Sreenivasaiah, Karteek
2
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
2
2018
Randomized communication versus partition number. Zbl 1427.68083
Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas
2
2018
The coin problem for product tests. Zbl 1427.68220
Lee, Chin Ho; Viola, Emanuele
2
2018
Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits. Zbl 1427.68111
Artemenko, Sergei; Shaltiel, Ronen
2
2017
Exact perfect matching in complete graphs. Zbl 1427.68243
Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Thierauf, Thomas
2
2017
On the power of amortization in secret sharing: \(d\)-uniform secret sharing and CDS with constant information rate. Zbl 07485440
Applebaum, Benny; Arkis, Barak
1
2020
Fast algorithms for general spin systems on bipartite expanders. Zbl 07499573
Galanis, Andreas; Goldberg, Leslie Ann; Stewart, James
1
2021
Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1485.68104
Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson
1
2019
Property testing of joint distributions using conditional samples. Zbl 1485.68306
Bhattacharyya, Rishiraj; Chakraborty, Sourav
1
2018
Strong locally testable codes with relaxed local decoders. Zbl 07143733
Goldreich, Oded; Gur, Tom; Komargodski, Ilan
1
2019
PPSZ for \(k\geq 5\): more is better. Zbl 07143741
Scheder, Dominik
1
2019
On approximate decidability of minimal programs. Zbl 1347.68096
Teutsch, Jason; Zimand, Marius
1
2015
Parameterized complexity and kernelizability of max ones and exact ones problems. Zbl 1347.68183
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
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
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
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
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
The complexity of approximating the matching polynomial in the complex plane. Zbl 07495903
Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel
3
2021
Fast algorithms for general spin systems on bipartite expanders. Zbl 07499573
Galanis, Andreas; Goldberg, Leslie Ann; Stewart, James
1
2021
On the power of amortization in secret sharing: \(d\)-uniform secret sharing and CDS with constant information rate. Zbl 07485440
Applebaum, Benny; Arkis, Barak
1
2020
New resolution-based QBF calculi and their proof complexity. Zbl 07143742
Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš
7
2019
New insights on the (non-)hardness of circuit minimization and related problems. Zbl 1441.68081
Allender, Eric; Hirahara, Shuichi
5
2019
Optimal sparsification for some binary CSPs using low-degree polynomials. Zbl 07143744
Jansen, Bart M. P.; Pieterse, Astrid
4
2019
The complexity of Boolean surjective general-valued CSPs. Zbl 1441.68091
Fulla, Peter; Uppman, Hannes; Živný, Stanislav
3
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
Lower bounds for sum and sum of products of read-once formulas. Zbl 1485.68095
Ramya, C.; Raghavendra Rao, B. V.
2
2019
Reconstruction of full rank algebraic branching programs. Zbl 1440.68080
Kayal, Neeraj; Nair, Vineet; Saha, Chandan; Tavenas, Sébastien
2
2019
Beyond worst-case (in)approximability of nonsubmodular influence maximization. Zbl 07143728
Schoenebeck, Grant; Tao, Biaoshuai
2
2019
Split contraction: the untold story. Zbl 07143734
Agrawal, Akanksha; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
2
2019
Approximating pairwise correlations in the Ising model. Zbl 07143739
Goldberg, Leslie Ann; Jerrum, Mark
2
2019
Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1485.68104
Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson
1
2019
Strong locally testable codes with relaxed local decoders. Zbl 07143733
Goldreich, Oded; Gur, Tom; Komargodski, Ilan
1
2019
PPSZ for \(k\geq 5\): more is better. Zbl 07143741
Scheder, Dominik
1
2019
Algorithmic information, plane Kakeya sets, and conditional dimension. Zbl 1427.68132
Lutz, Jack H.; Lutz, Neil
6
2018
Directed multicut is W[1]-hard, even for four terminal pairs. Zbl 1427.68252
Pilipczuk, Marcin; Wahlström, Magnus
5
2018
Tight running time lower bounds for vertex deletion problems. Zbl 1427.68245
Komusiewicz, Christian
3
2018
Invariance principle on the slice. Zbl 1427.60018
Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl
3
2018
Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. Zbl 1485.68107
Guo, Heng; Lu, Pinyan
2
2018
Simultaneous feedback vertex set: a parameterized perspective. Zbl 1485.68169
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
2
2018
Randomized communication versus partition number. Zbl 1427.68083
Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas
2
2018
The coin problem for product tests. Zbl 1427.68220
Lee, Chin Ho; Viola, Emanuele
2
2018
Property testing of joint distributions using conditional samples. Zbl 1485.68306
Bhattacharyya, Rishiraj; Chakraborty, Sourav
1
2018
Hardness of approximation for \(H\)-free edge modification problems. Zbl 1427.68105
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał
1
2018
Complete derandomization of identity testing and reconstruction of read-once formulas. Zbl 1427.68363
Minahan, Daniel; Volkovich, Ilya
1
2018
The limits of SDP relaxations for general-valued CSPs. Zbl 1427.90245
Thapper, Johan; Živný, Stanislav
1
2018
Asking the metaquestions in constraint tractability. Zbl 1427.68115
Chen, Hubie; Larose, Benoit
6
2017
A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121
Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark
4
2017
On space efficiency of algorithms working on structural decompositions of graphs. Zbl 1427.68130
Pilipczuk, Michał; Wrochna, Marcin
4
2017
Finding consensus strings with small length difference between input and solution strings. Zbl 1427.68131
Schmid, Markus L.
3
2017
Hardness of approximation for strip packing. Zbl 1427.68100
Adamaszek, Anna; Kociumaka, Tomasz; Pilipczuk, Marcin; Pilipczuk, Michał
3
2017
Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits. Zbl 1427.68111
Artemenko, Sergei; Shaltiel, Ronen
2
2017
Exact perfect matching in complete graphs. Zbl 1427.68243
Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Thierauf, Thomas
2
2017
Lower bounds for constant query affine-invariant LCCs and LTCs. Zbl 1427.94088
Bhattacharyya, Arnab; Gopi, Sivakanth
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
27
2016
Characterizing arithmetic read-once formulae. Zbl 1347.68148
Volkovich, Ilya
8
2016
On sample-based testers. Zbl 1427.68360
Goldreich, Oded; Ron, Dana
4
2016
Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
3
2016
A Galois connection for weighted (relational) clones of infinite size. Zbl 1427.68120
Fulla, Peter; Živný, Stanislav
2
2016
The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362
Haviv, Ishay; Regev, Oded
2
2016
Space-efficient approximations for subset sum. Zbl 1427.68367
Gál, Anna; Jang, Jing-Tang; Limaye, Nutan; Mahajan, Meena; Sreenivasaiah, Karteek
2
2016
Parameterized complexity and kernelizability of max ones and exact ones problems. Zbl 1347.68183
Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus
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
Tractable parameterizations for the minimum linear arrangement problem. Zbl 1427.68118
Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances; Shachnai, Hadas
1
2016
The power of an example: hidden set size approximation using group queries and conditional sampling. Zbl 1427.68221
Ron, Dana; Tsur, Gilad
1
2016
Quadratic maps are hard to sample. Zbl 1427.68109
Viola, Emanuele
1
2016
On hardness of multilinearization and VNP-completeness in characteristic 2. Zbl 1427.68107
Hrubeš, P.
1
2016
Some hard families of parameterized counting problems. Zbl 1348.68066
Jerrum, Mark; Meeks, Kitty
9
2015
Exploring the subexponential complexity of completion problems. Zbl 1347.68180
Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve
8
2015
Quantum XOR games. Zbl 1348.81177
Regev, Oded; Vidick, Thomas
7
2015
Mutual dimension. Zbl 1348.03041
Case, Adam; Lutz, Jack H.
7
2015
The fine classification of conjunctive queries and parameterized logarithmic space. Zbl 1347.68179
Chen, Hubie; Müller, Moritz
3
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
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
30
2014
Optimal lower bounds for locality-sensitive hashing (except when \(q\) is tiny). Zbl 1320.68095
O’Donnell, Ryan; Wu, Yi; Zhou, Yuan
13
2014
On the one-way function candidate proposed by Goldreich. Zbl 1347.94029
Cook, James; Etesami, Omid; Miller, Rachel; Trevisan, Luca
7
2014
Clique cover and graph separation: new incompressibility results. Zbl 1321.68302
Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus
6
2014
The hardness of being private. Zbl 1321.94032
Ada, Anil; Chattopadhyay, Arkadev; Cook, Stephen A.; Fontes, Lila; Koucký, Michal; Pitassi, Toniann
6
2014
The complexity of the nucleolus in compact games. Zbl 1348.91073
Greco, Gianluigi; Malizia, Enrico; Palopoli, Luigi; Scarcello, Francesco
5
2014
The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181
Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David
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 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
The complexity of the comparator circuit value problem. Zbl 1347.68156
Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man
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
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 effective convergence of numerical solutions for differential equations. Zbl 1321.03056
Sun, Shu-Ming; Zhong, Ning
1
2014
On multiway cut parameterized above lower bounds. Zbl 1322.68098
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry
39
2013
Compressed matrix multiplication. Zbl 1322.65055
Pagh, Rasmus
13
2013
Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099
Dalmau, Víctor; Krokhin, Andrei
12
2013
Real advantage. Zbl 1322.68076
Razborov, Alexander; Viola, Emanuele
5
2013
Distortion is fixed parameter tractable. Zbl 1322.68102
Fellows, Michael; Fomin, Fedor V.; Lokshtanov, Daniel; Losievskaja, Elena; Rosamond, Frances; Saurabh, Saket
4
2013
On the usefulness of predicates. Zbl 1322.68093
Austrin, Per; Håstad, Johan
3
2013
Quantum rejection sampling. Zbl 1322.68079
Ozols, Maris; Roetteler, Martin; Roland, Jérémie
3
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
Complexity theory for operators in analysis. Zbl 1322.68083
Kawamura, Akitoshi; Cook, Stephen
14
2012
The computational complexity of Nash equilibria in concisely represented games. Zbl 1322.68110
Schoenebeck, Grant R.; Vadhan, Salil
12
2012
Exact quantum algorithms for the leader election problem. Zbl 1322.68077
Tani, Seiichiro; Kobayashi, Hirotada; Matsumoto, Keiji
7
2012
Parameterized bounded-depth Frege is not optimal. Zbl 1322.68082
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo; Razborov, Alexander A.
6
2012
Collusion-resistant mechanisms with verification yielding optimal solutions. Zbl 1322.68255
Penna, Paolo; Ventre, Carmine
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
...and 14 more Documents
all top 5

Cited by 825 Authors

11 Pilipczuk, Marcin L.
10 Saurabh, Saket
9 Pilipczuk, Michał
9 Živný, Stanislav
7 Jansen, Bart M. P.
6 Beyersdorff, Olaf
6 Datta, Samir
6 Goldberg, Leslie Ann
6 Gur, Tom
6 Lutz, Neil
6 Marx, Dániel
6 Raghavendra Rao, B. V.
6 Roth, Marc
5 Allender, Eric W.
5 Applebaum, Benny
5 Pieterse, Astrid
5 Schmitt, Johannes
5 Schmitz, Sylvain
5 Steinberg, Florian
5 Stull, Donald M.
5 Tewari, Raghunath
5 Van Leeuwen, Erik Jan
5 Vinodchandran, N. Variyam
4 Chen, Hubie
4 Chitnis, Rajesh Hemant
4 Cygan, Marek
4 Fluschnik, Till
4 Galanis, Andreas
4 Göös, Mika
4 Greco, Gianluigi
4 Ishai, Yuval
4 Kawamura, Akitoshi
4 Kratsch, Stefan
4 Krokhin, Andrei A.
4 Lazić, Ranko
4 Lokshtanov, Daniel
4 Mahajan, Meena
4 Niedermeier, Rolf
4 Palazuelos, Carlos
4 Tu, Jianhua
4 van Bevern, René
4 Viola, Emanuele
4 Woodruff, David P.
4 Ziegler, Martin
3 Altman, Harry J.
3 Blinkhorn, Joshua
3 Brandt, Felix
3 Chiesa, Alessandro
3 Fischer, Felix
3 Göbel, Andreas-Nikolas
3 Guruswami, Venkatesan
3 Hermelin, Danny
3 Iwata, Yoichi
3 Komusiewicz, Christian
3 Kozik, Marcin
3 Kulkarni, Raghav
3 Lauria, Massimo
3 Li, Shaohua
3 Lovett, Shachar
3 Meeks, Kitty
3 Mnich, Matthias
3 Molter, Hendrik
3 Panolan, Fahad
3 Pratt-Hartmann, Ian
3 Raman, Venkatesh
3 Ramanujan, M. S.
3 Rothblum, Ron D.
3 Sarma M. N., Jayalal
3 Sau, Ignasi
3 Servedio, Rocco A.
3 Sunil, K. S.
3 Tendera, Lidia
3 Thaler, Justin
3 Thapper, Johan
3 Thierauf, Thomas
3 Wahlström, Magnus
3 Weinstein, Omri
3 Wellnitz, Philip
3 Zehavi, Meirav
2 Agrawal, Akanksha
2 Balla, Igor
2 Birmele, Etienne
2 Bitansky, Nir
2 Bodlaender, Hans L.
2 Bulatov, Andrei A.
2 Bulteau, Laurent
2 Campos, Victor A.
2 Canteaut, Anne
2 Cao, Yixin
2 Carpov, Sergiu
2 Chakrabarti, Amit
2 Chen, Jian-er
2 Chen, Lijie
2 Chen, Xi
2 Cheon, Jung Hee
2 Dalmau, Víctor
2 Damaschke, Peter
2 Dantchev, Stefan Stoyanov
2 de Montgolfier, Fabien
2 Demri, Stéphane P.
...and 725 more Authors
all top 5

Cited in 91 Journals

38 SIAM Journal on Computing
30 Algorithmica
25 Theoretical Computer Science
20 Computational Complexity
20 Theory of Computing Systems
19 Journal of Computer and System Sciences
13 SIAM Journal on Discrete Mathematics
10 Information and Computation
8 Artificial Intelligence
7 Logical Methods in Computer Science
6 Information Processing Letters
6 Journal of Cryptology
4 Discrete Applied Mathematics
4 SIAM Journal on Matrix Analysis and Applications
3 Israel Journal of Mathematics
3 Journal of Automated Reasoning
3 Cybernetics and Systems Analysis
3 Journal of Machine Learning Research (JMLR)
3 ACM Transactions on Computational Logic
2 Acta Informatica
2 Communications in Mathematical Physics
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 Computers & Operations Research
2 International Journal of Algebra and Computation
2 MSCS. Mathematical Structures in Computer Science
2 International Journal of Foundations of Computer Science
2 Journal of Discrete Algorithms
2 Journal of Mathematical Cryptology
2 Computability
2 Discrete Analysis
1 International Journal of Theoretical Physics
1 Journal of Mathematical Analysis and Applications
1 Journal of Mathematical Physics
1 Journal of Statistical Physics
1 The Annals of Statistics
1 Applied Mathematics and Computation
1 Journal of Algebra
1 Journal of Combinatorial Theory. Series B
1 Journal of Functional Analysis
1 Journal of the Korean Mathematical Society
1 Mathematics of Operations Research
1 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 Applied Mathematics Letters
1 Journal of the American Mathematical Society
1 Formal Aspects of Computing
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 Annals of Mathematics and Artificial Intelligence
1 Complexity
1 Discussiones Mathematicae. Graph Theory
1 Electronic Journal of Probability
1 INFORMS Journal on Computing
1 Soft Computing
1 Journal of Combinatorial Optimization
1 Journal of Scheduling
1 Journal of the ACM
1 International Journal of Applied Mathematics and Computer Science
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 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Theory of Computing
1 Information and Inference
1 Moscow Journal of Combinatorics and Number Theory
1 Forum of Mathematics, Pi
1 Forum of Mathematics, Sigma
1 ACM Transactions on Computation Theory
1 Prikladnaya Diskretnaya Matematika
1 Advances in Combinatorics
1 SIAM Journal on Mathematics of Data Science

Citations by Year