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: Journal; Indexed cover-to-cover Documents Indexed: 228 Publications (since 2009) References Indexed: 37 Publications with 947 References. all top 5 Latest Issues 14, No. 1 (2022) 13, No. 4 (2021) 13, No. 3 (2021) 13, No. 2 (2021) 13, No. 1 (2021) 12, No. 4 (2020) 12, No. 3 (2020) 12, No. 2 (2020) 12, No. 1 (2020) 11, No. 4 (2019) 11, No. 3 (2019) 11, No. 2 (2019) 11, No. 1 (2019) 10, No. 4 (2018) 10, No. 3 (2018) 10, No. 2 (2018) 10, No. 1 (2018) 9, No. 4 (2017) 9, No. 3 (2017) 9, No. 2 (2017) 9, No. 1 (2016) 8, No. 4 (2016) 8, No. 3 (2016) 8, No. 2 (2016) 8, No. 1 (2016) 7, No. 4 (2015) 7, No. 3 (2015) 7, No. 2 (2015) 7, No. 1 (2014) 6, No. 4 (2014) 6, No. 3 (2014) 6, No. 2 (2014) 6, No. 1 (2014) 5, No. 4 (2013) 5, No. 3 (2013) 5, No. 2 (2013) 5, No. 1 (2013) 4, No. 4 (2012) 4, No. 3 (2012) 4, No. 2 (2012) 4, No. 1 (2012) 3, No. 2 (2012) 3, No. 1 (2011) 2, No. 2 (2011) 2, No. 1 (2010) 1, No. 3 (2010) 1, No. 2 (2009) 1, No. 1 (2009) all top 5 Authors 8 Goldberg, Leslie Ann 8 Pilipczuk, Michał 8 Saurabh, Saket 8 Viola, Emanuele 7 Ron, Dana 6 Lokshtanov, Daniel 6 Živný, Stanislav 5 Pilipczuk, Marcin L. 5 Pitassi, Toniann 5 Wahlström, Magnus 4 Beyersdorff, Olaf 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 Wrochna, Marcin 4 Zehavi, Meirav 3 Beame, Paul W. 3 Chen, Hubie 3 Cygan, Marek 3 Filmus, Yuval 3 Galanis, Andreas 3 Göbel, Andreas-Nikolas 3 Gurjar, Rohit 3 Håstad, Johan Torkel 3 Kayal, Neeraj 3 Kerenidis, Iordanis 3 Kratsch, Stefan 3 Lagerkvist, Victor 3 Raskhodnikova, Sofya 3 Razborov, Aleksandr Aleksandrovich 3 Saha, Chandan 3 Sreenivasaiah, Karteek 3 Torán, Jacobo 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 Chattopadhyay, Arkadev 2 Cheraghchi, Mahdi 2 Datta, Samir 2 De, Anindya K. 2 Fernau, Henning 2 Fontes, Lila 2 Fulla, Peter 2 Gál, Anna 2 Galesi, Nicola 2 Ganardi, Moses 2 Göös, Mika 2 Gur, Tom 2 Haviv, Ishay 2 Iwama, Kazuo 2 Jansen, Bart M. P. 2 Kabanets, Valentine 2 Kolay, Sudeshna 2 Koroth, Sajin 2 Korwar, Arpita 2 Koucký, Michal 2 Krebs, Andreas 2 Kulkarni, Raghav 2 Kumar, Mrinal 2 Lachish, Oded 2 Larose, Benoit 2 Lauria, Massimo 2 Lee, Chin Ho 2 Levi, Amit 2 Lohrey, Markus 2 Lu, Zhenjian 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 Myrisiotis, Dimitrios 2 Nair, Vineet 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 Santhanam, Rahul 2 Schmid, Markus L. 2 Schoenebeck, Grant R. ...and 296 more Authors all top 5 Fields 221 Computer science (68-XX) 39 Combinatorics (05-XX) 21 Mathematical logic and foundations (03-XX) 20 Information and communication theory, circuits (94-XX) 14 Operations research, mathematical programming (90-XX) 14 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 9 General algebraic systems (08-XX) 5 Number theory (11-XX) 5 Probability theory and stochastic processes (60-XX) 5 Numerical analysis (65-XX) 4 Quantum theory (81-XX) 3 Order, lattices, ordered algebraic structures (06-XX) 3 Statistical mechanics, structure of matter (82-XX) 2 Field theory and polynomials (12-XX) 2 Associative rings and algebras (16-XX) 2 Group theory and generalizations (20-XX) 2 Measure and integration (28-XX) 1 General and overarching topics; collections (00-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Approximations and expansions (41-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Biology and other natural sciences (92-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 157 Publications have been cited 765 times in 691 Documents Cited by ▼ Year ▼ (Leveled) fully homomorphic encryption without bootstrapping. Zbl 1347.68121 Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod 60 2014 On multiway cut parameterized above lower bounds. Zbl 1322.68098 Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; Wojtaszczyk, Jakub Onufry 43 2013 Complexity hierarchies beyond elementary. Zbl 1347.68162 Schmitz, Sylvain 33 2016 Algebrization: a new barrier in complexity theory. Zbl 1322.68080 Aaronson, Scott; Wigderson, Avi 31 2009 Directed planar reachability is in unambiguous log-space. Zbl 1322.68095 Bourke, Chris; Tewari, Raghunath; Vinodchandran, N. V. 20 2009 Complexity theory for operators in analysis. Zbl 1322.68083 Kawamura, Akitoshi; Cook, Stephen 19 2012 The computational complexity of Nash equilibria in concisely represented games. Zbl 1322.68110 Schoenebeck, Grant R.; Vadhan, Salil 16 2012 Compressed matrix multiplication. Zbl 1322.65055 Pagh, Rasmus 16 2013 Optimal lower bounds for locality-sensitive hashing (except when \(q\) is tiny). Zbl 1320.68095 O’Donnell, Ryan; Wu, Yi; Zhou, Yuan 15 2014 New resolution-based QBF calculi and their proof complexity. Zbl 1496.68362 Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš 14 2019 Robust satisfiability for CSPs: hardness and algorithmic results. Zbl 1322.68099 Dalmau, Víctor; Krokhin, Andrei 13 2013 Exploring the subexponential complexity of completion problems. Zbl 1347.68180 Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michał; Villanger, Yngve 13 2015 A simple proof of Bazzi’s theorem. Zbl 1322.68108 Razborov, Alexander 12 2009 Quantum XOR games. Zbl 1348.81177 Regev, Oded; Vidick, Thomas 12 2015 Algorithmic information, plane Kakeya sets, and conditional dimension. Zbl 1427.68132 Lutz, Jack H.; Lutz, Neil 12 2018 Clique cover and graph separation: new incompressibility results. Zbl 1321.68302 Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Wahlström, Magnus 10 2014 Some hard families of parameterized counting problems. Zbl 1348.68066 Jerrum, Mark; Meeks, Kitty 10 2015 Real advantage. Zbl 1322.68076 Razborov, Alexander; Viola, Emanuele 9 2013 On the one-way function candidate proposed by Goldreich. Zbl 1347.94029 Cook, James; Etesami, Omid; Miller, Rachel; Trevisan, Luca 9 2014 Asking the metaquestions in constraint tractability. Zbl 1427.68115 Chen, Hubie; Larose, Benoit 9 2017 Characterizing arithmetic read-once formulae. Zbl 1347.68148 Volkovich, Ilya 8 2016 Mutual dimension. Zbl 1348.03041 Case, Adam; Lutz, Jack H. 8 2015 Directed multicut is W[1]-hard, even for four terminal pairs. Zbl 1427.68252 Pilipczuk, Marcin; Wahlström, Magnus 8 2018 Exact quantum algorithms for the leader election problem. Zbl 1322.68077 Tani, Seiichiro; Kobayashi, Hirotada; Matsumoto, Keiji 7 2012 Quantum rejection sampling. Zbl 1322.68079 Ozols, Maris; Roetteler, Martin; Roland, Jérémie 7 2013 Distortion is fixed parameter tractable. Zbl 1322.68102 Fellows, Michael; Fomin, Fedor V.; Lokshtanov, Daniel; Losievskaja, Elena; Rosamond, Frances; Saurabh, Saket 7 2013 On sample-based testers. Zbl 1427.68360 Goldreich, Oded; Ron, Dana 7 2016 Split contraction: the untold story. Zbl 1496.68260 Agrawal, Akanksha; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav 7 2019 New insights on the (non-)hardness of circuit minimization and related problems. Zbl 1441.68081 Allender, Eric; Hirahara, Shuichi 7 2019 Tight complexity lower bounds for integer linear programming with few constraints. Zbl 1499.68133 Knop, Dušan; Pilipczuk, Michał; Wrochna, Marcin 7 2020 The hardness of being private. Zbl 1321.94032 Ada, Anil; Chattopadhyay, Arkadev; Cook, Stephen A.; Fontes, Lila; Koucký, Michal; Pitassi, Toniann 6 2014 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 Tight running time lower bounds for vertex deletion problems. Zbl 1427.68245 Komusiewicz, Christian 6 2018 Hardness of approximation for strip packing. Zbl 1427.68100 Adamaszek, Anna; Kociumaka, Tomasz; Pilipczuk, Marcin; Pilipczuk, Michał 6 2017 Optimal sparsification for some binary CSPs using low-degree polynomials. Zbl 1495.68100 Jansen, Bart M. P.; Pieterse, Astrid 6 2019 Sound 3-query PCPPs are long. Zbl 1322.68094 Ben-Sasson, Eli; Harsha, Prahladh; Lachish, Oded; Matsliah, Arie 5 2009 Planarity, determinants, permanents, and (unique) matchings. Zbl 1322.05088 Datta, Samir; Kulkarni, Raghav; Limaye, Nutan; Mahajan, Meena 5 2010 On the computational complexity of stochastic controller optimization in POMDPs. Zbl 1322.68111 Vlassis, Nikos; Littman, Michael L.; Barber, David 5 2012 The complexity of counting homomorphisms to cactus graphs modulo 2. Zbl 1347.68181 Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David 5 2014 The complexity of the nucleolus in compact games. Zbl 1348.91073 Greco, Gianluigi; Malizia, Enrico; Palopoli, Luigi; Scarcello, Francesco 5 2014 The fine classification of conjunctive queries and parameterized logarithmic space. Zbl 1347.68179 Chen, Hubie; Müller, Moritz 5 2015 Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241 Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David 5 2016 Invariance principle on the slice. Zbl 1427.60018 Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl 5 2018 On space efficiency of algorithms working on structural decompositions of graphs. Zbl 1427.68130 Pilipczuk, Michał; Wrochna, Marcin 5 2017 Distribution testing lower bounds via reductions from communication complexity. Zbl 1440.68323 Blais, Eric; Canonne, Clément L.; Gur, Tom 5 2019 Logspace reduction of directed reachability for bounded genus graphs to the planar case. Zbl 1322.68107 Kynčl, Jan; Vyskočil, Tomáš 4 2010 Formula caching in DPLL. Zbl 1322.68175 Beame, Paul; Impagliazzo, Russell; Pitassi, Toniann; Segerlind, Nathan 4 2010 Collusion-resistant mechanisms with verification yielding optimal solutions. Zbl 1322.68255 Penna, Paolo; Ventre, Carmine 4 2012 On the sum of square roots of polynomials and related problems. Zbl 1322.68104 Kayal, Neeraj; Saha, Chandan 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 4 2012 On the usefulness of predicates. Zbl 1322.68093 Austrin, Per; Håstad, Johan 4 2013 FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders. Zbl 1347.68167 Fellows, Michael R.; Jansen, Bart M. P. 4 2014 Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. Zbl 1347.68171 Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh 4 2014 A Galois connection for weighted (relational) clones of infinite size. Zbl 1427.68120 Fulla, Peter; Živný, Stanislav 4 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 4 2018 A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121 Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark 4 2017 Finding consensus strings with small length difference between input and solution strings. Zbl 1427.68131 Schmid, Markus L. 4 2017 Simultaneous feedback vertex set: a parameterized perspective. Zbl 1485.68169 Agrawal, Akanksha; Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket 4 2018 The complexity of Boolean surjective general-valued CSPs. Zbl 1441.68091 Fulla, Peter; Uppman, Hannes; Živný, Stanislav 4 2019 Sparsification of SAT and CSP problems via tractable extensions. Zbl 1499.68241 Lagerkvist, Victor; Wahlström, Magnus 4 2020 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 Parameterized complexity and kernelizability of max ones and exact ones problems. Zbl 1347.68183 Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus 3 2016 The complexity of the comparator circuit value problem. Zbl 1347.68156 Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man 3 2014 Randomized communication versus partition number. Zbl 1427.68083 Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas 3 2018 Hardness of approximation for \(H\)-free edge modification problems. Zbl 1427.68105 Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał 3 2018 Exact perfect matching in complete graphs. Zbl 1427.68243 Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Thierauf, Thomas 3 2017 Proof complexity modulo the polynomial hierarchy: understanding alternation as a source of hardness. Zbl 1427.03063 Chen, Hubie 3 2017 Metric 1-median selection: query complexity vs. approximation ratio. Zbl 1427.68114 Chang, Ching-Lueh 3 2017 Fine-grained time complexity of constraint satisfaction problems. Zbl 1495.68101 Jonsson, Peter; Lagerkvist, Victor; Roy, Biman 3 2021 The complexity of approximating the matching polynomial in the complex plane. Zbl 1495.68163 Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel 3 2021 Fast algorithms for general spin systems on bipartite expanders. Zbl 1495.68170 Galanis, Andreas; Goldberg, Leslie Ann; Stewart, James 3 2021 The complexity of promise SAT on non-Boolean domains. Zbl 1495.68157 Brandts, Alex; Wrochna, Marcin; Živný, Stanislav 3 2021 Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1485.68104 Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson 3 2019 Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. Zbl 1485.68107 Guo, Heng; Lu, Pinyan 3 2018 Reconstruction of full rank algebraic branching programs. Zbl 1440.68080 Kayal, Neeraj; Nair, Vineet; Saha, Chandan; Tavenas, Sébastien 3 2019 Beyond worst-case (in)approximability of nonsubmodular influence maximization. Zbl 1495.91096 Schoenebeck, Grant; Tao, Biaoshuai 3 2019 On minrank and forbidden subgraphs. Zbl 1498.05164 Haviv, Ishay 3 2019 Approximating pairwise correlations in the Ising model. Zbl 1498.82006 Goldberg, Leslie Ann; Jerrum, Mark 3 2019 Reasons for hardness in QBF proof systems. Zbl 1499.03053 Beyersdorff, Olaf; Hinde, Luke; Pich, Ján 3 2020 Circuit lower bounds for MCSP from local pseudorandom generators. Zbl 1499.68102 Cheraghchi, Mahdi; Kabanets, Valentine; Lu, Zhenjian; Myrisiotis, Dimitrios 3 2020 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 2 2014 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 Extractors and lower bounds for locally samplable sources. Zbl 1322.65009 De, Anindya; Watson, Thomas 2 2012 High-confidence predictions under adversarial uncertainty. Zbl 1322.68266 Drucker, Andrew 2 2013 On approximate decidability of minimal programs. Zbl 1347.68096 Teutsch, Jason; Zimand, Marius 2 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 2 2016 Evolvability of real functions. Zbl 1347.68314 Valiant, Paul 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 Tractable parameterizations for the minimum linear arrangement problem. Zbl 1427.68118 Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances; Shachnai, Hadas 2 2016 The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362 Haviv, Ishay; Regev, Oded 2 2016 The power of an example: hidden set size approximation using group queries and conditional sampling. Zbl 1427.68221 Ron, Dana; Tsur, Gilad 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 Quadratic maps are hard to sample. Zbl 1427.68109 Viola, Emanuele 2 2016 Ground state connectivity of local Hamiltonians. Zbl 1427.68086 Gharibian, Sevag; Sikora, Jamie 2 2018 Complete derandomization of identity testing and reconstruction of read-once formulas. Zbl 1427.68363 Minahan, Daniel; Volkovich, Ilya 2 2018 The limits of SDP relaxations for general-valued CSPs. Zbl 1427.90245 Thapper, Johan; Živný, Stanislav 2 2018 Optimal distribution-free sample-based testing of subsequence-freeness with one-sided error. Zbl 1495.68248 Ron, Dana; Rosin, Asaf 1 2022 Fine-grained time complexity of constraint satisfaction problems. Zbl 1495.68101 Jonsson, Peter; Lagerkvist, Victor; Roy, Biman 3 2021 The complexity of approximating the matching polynomial in the complex plane. Zbl 1495.68163 Bezáková, Ivona; Galanis, Andreas; Goldberg, Leslie Ann; Štefankovič, Daniel 3 2021 Fast algorithms for general spin systems on bipartite expanders. Zbl 1495.68170 Galanis, Andreas; Goldberg, Leslie Ann; Stewart, James 3 2021 The complexity of promise SAT on non-Boolean domains. Zbl 1495.68157 Brandts, Alex; Wrochna, Marcin; Živný, Stanislav 3 2021 Improved bounds on Fourier entropy and min-entropy. Zbl 1498.94110 Arunachalam, Srinivasan; Chakraborty, Sourav; Koucký, Michal; Saurabh, Nitin; De Wolf, Ronald 2 2021 On the parameterized approximability of contraction to classes of chordal graphs. Zbl 1495.68178 Gunda, Spoorthy; Jain, Pallavi; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar 2 2021 Fractal intersections and products via algorithmic dimension. Zbl 1495.68104 Lutz, Neil 2 2021 Multiplicative parameterization above a guarantee. Zbl 1495.68103 Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav 2 2021 Complexity of shift bribery in committee elections. Zbl 1498.91177 Bredereck, Robert; Faliszewski, Piotr; Niedermeier, Rolf; Talmon, Nimrod 2 2021 Lower bounding the AND-OR tree via symmetrization. Zbl 1495.68095 Kretschmer, William 1 2021 Fine-grained reductions from approximate counting to decision. Zbl 1495.68098 Dell, Holger; Lapinskas, John 1 2021 Popular matching in roommates setting is NP-hard. Zbl 1495.68093 Gupta, Sushmita; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav 1 2021 On a theorem of Lovász that \((\cdot, H)\) determines the isomorphism type of \(H\). Zbl 1506.05142 Cai, Jin-yi; Govorov, Artem 1 2021 On the sensitivity complexity of \(k\)-uniform hypergraph properties. Zbl 1495.68102 Li, Qian; Sun, Xiaoming 1 2021 Variants of homomorphism polynomials complete for algebraic complexity classes. Zbl 1495.68060 Chaugule, Prasad; Limaye, Nutan; Varre, Aditya 1 2021 Sign-rank can increase under intersection. Zbl 1495.68080 Bun, Mark; Mande, Nikhil S.; Thaler, Justin 1 2021 Tight complexity lower bounds for integer linear programming with few constraints. Zbl 1499.68133 Knop, Dušan; Pilipczuk, Michał; Wrochna, Marcin 7 2020 Sparsification of SAT and CSP problems via tractable extensions. Zbl 1499.68241 Lagerkvist, Victor; Wahlström, Magnus 4 2020 Reasons for hardness in QBF proof systems. Zbl 1499.03053 Beyersdorff, Olaf; Hinde, Luke; Pich, Ján 3 2020 Circuit lower bounds for MCSP from local pseudorandom generators. Zbl 1499.68102 Cheraghchi, Mahdi; Kabanets, Valentine; Lu, Zhenjian; Myrisiotis, Dimitrios 3 2020 A \(\mathrm{ZPP}^{\mathrm{NP[1]}}\) lifting theorem. Zbl 1495.68091 Watson, Thomas 2 2020 Search versus decision for election manipulation problems. Zbl 1499.91039 Hemaspaandra, Edith; Hemaspaandra, Lane A.; Menton, Curtis 2 2020 Cops-robber games and the resolution of Tseitin formulas. Zbl 1499.03055 Galesi, Nicola; Talebanfard, Navid; Torán, Jacobo 2 2020 Strongly exponential separation between monotone VP and monotone VNP. Zbl 1495.68067 Srinivasan, Srikanth 1 2020 On the power of amortization in secret sharing: \(d\)-uniform secret sharing and CDS with constant information rate. Zbl 1495.94077 Applebaum, Benny; Arkis, Barak 1 2020 Inner product and set disjointness: beyond logarithmically many parties. Zbl 1495.68084 Podolskii, Vladimir V.; Sherstov, Alexander A. 1 2020 Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth-three circuits. Zbl 1499.68100 Kayal, Neeraj; Nair, Vineet; Saha, Chandan 1 2020 On the power of border of depth-3 arithmetic circuits. Zbl 1499.68106 Kumar, Mrinal 1 2020 Pattern matching with variables: efficient algorithms and complexity results. Zbl 1499.68422 Fernau, Henning; Manea, Florin; Mercaş, Robert; Schmid, Markus L. 1 2020 Approximate counting CSP seen from the other side. Zbl 1499.68239 Bulatov, Andrei A.; Živný, Stanislav 1 2020 New resolution-based QBF calculi and their proof complexity. Zbl 1496.68362 Beyersdorff, Olaf; Chew, Leroy; Janota, Mikoláš 14 2019 Split contraction: the untold story. Zbl 1496.68260 Agrawal, Akanksha; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav 7 2019 New insights on the (non-)hardness of circuit minimization and related problems. Zbl 1441.68081 Allender, Eric; Hirahara, Shuichi 7 2019 Optimal sparsification for some binary CSPs using low-degree polynomials. Zbl 1495.68100 Jansen, Bart M. P.; Pieterse, Astrid 6 2019 Distribution testing lower bounds via reductions from communication complexity. Zbl 1440.68323 Blais, Eric; Canonne, Clément L.; Gur, Tom 5 2019 The complexity of Boolean surjective general-valued CSPs. Zbl 1441.68091 Fulla, Peter; Uppman, Hannes; Živný, Stanislav 4 2019 Gadgets and anti-gadgets leading to a complexity dichotomy. Zbl 1485.68104 Cai, Jin-Yi; Kowalczyk, Michael; Williams, Tyson 3 2019 Reconstruction of full rank algebraic branching programs. Zbl 1440.68080 Kayal, Neeraj; Nair, Vineet; Saha, Chandan; Tavenas, Sébastien 3 2019 Beyond worst-case (in)approximability of nonsubmodular influence maximization. Zbl 1495.91096 Schoenebeck, Grant; Tao, Biaoshuai 3 2019 On minrank and forbidden subgraphs. Zbl 1498.05164 Haviv, Ishay 3 2019 Approximating pairwise correlations in the Ising model. Zbl 1498.82006 Goldberg, Leslie Ann; Jerrum, Mark 3 2019 Lower bounds for sum and sum of products of read-once formulas. Zbl 1485.68095 Ramya, C.; Raghavendra Rao, B. V. 2 2019 Surjective H-colouring over reflexive digraphs. Zbl 1485.68190 Larose, Benoît; Martin, Barnaby; Paulusma, Daniël 1 2019 Tight lower bounds for the complexity of multicoloring. Zbl 1434.68185 Bonamy, Marthe; Kowalik, Łukasz; Pilipczuk, Michał; Socała, Arkadiusz; Wrochna, Marcin 1 2019 Strong locally testable codes with relaxed local decoders. Zbl 1495.94159 Goldreich, Oded; Gur, Tom; Komargodski, Ilan 1 2019 Tolerant junta testing and the connection to submodular optimization and function isomorphism. Zbl 1495.68245 Blais, Eric; Canonne, Clément L.; Eden, Talya; Levi, Amit; Ron, Dana 1 2019 PPSZ for \(k\geq 5\): more is better. Zbl 1496.68259 Scheder, Dominik 1 2019 Algorithmic information, plane Kakeya sets, and conditional dimension. Zbl 1427.68132 Lutz, Jack H.; Lutz, Neil 12 2018 Directed multicut is W[1]-hard, even for four terminal pairs. Zbl 1427.68252 Pilipczuk, Marcin; Wahlström, Magnus 8 2018 Tight running time lower bounds for vertex deletion problems. Zbl 1427.68245 Komusiewicz, Christian 6 2018 Invariance principle on the slice. Zbl 1427.60018 Filmus, Yuval; Kindler, Guy; Mossel, Elchanan; Wimmer, Karl 5 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 4 2018 Simultaneous feedback vertex set: a parameterized perspective. Zbl 1485.68169 Agrawal, Akanksha; Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket 4 2018 Randomized communication versus partition number. Zbl 1427.68083 Göös, Mika; Jayram, T. S.; Pitassi, Toniann; Watson, Thomas 3 2018 Hardness of approximation for \(H\)-free edge modification problems. Zbl 1427.68105 Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał 3 2018 Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems. Zbl 1485.68107 Guo, Heng; Lu, Pinyan 3 2018 Ground state connectivity of local Hamiltonians. Zbl 1427.68086 Gharibian, Sevag; Sikora, Jamie 2 2018 Complete derandomization of identity testing and reconstruction of read-once formulas. Zbl 1427.68363 Minahan, Daniel; Volkovich, Ilya 2 2018 The limits of SDP relaxations for general-valued CSPs. Zbl 1427.90245 Thapper, Johan; Živný, Stanislav 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 Streaming communication protocols. Zbl 1442.68012 Boczkowski, Lucas; Kerenidis, Iordanis; Magniez, Frédéric 1 2018 Asking the metaquestions in constraint tractability. Zbl 1427.68115 Chen, Hubie; Larose, Benoit 9 2017 Hardness of approximation for strip packing. Zbl 1427.68100 Adamaszek, Anna; Kociumaka, Tomasz; Pilipczuk, Marcin; Pilipczuk, Michał 6 2017 On space efficiency of algorithms working on structural decompositions of graphs. Zbl 1427.68130 Pilipczuk, Michał; Wrochna, Marcin 5 2017 A complexity trichotomy for approximately counting list \(H\)-colorings. Zbl 1427.68121 Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark 4 2017 Finding consensus strings with small length difference between input and solution strings. Zbl 1427.68131 Schmid, Markus L. 4 2017 Exact perfect matching in complete graphs. Zbl 1427.68243 Gurjar, Rohit; Korwar, Arpita; Messner, Jochen; Thierauf, Thomas 3 2017 Proof complexity modulo the polynomial hierarchy: understanding alternation as a source of hardness. Zbl 1427.03063 Chen, Hubie 3 2017 Metric 1-median selection: query complexity vs. approximation ratio. Zbl 1427.68114 Chang, Ching-Lueh 3 2017 Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits. Zbl 1427.68111 Artemenko, Sergei; Shaltiel, Ronen 2 2017 Parameterized testability. Zbl 1427.68124 Iwama, Kazuo; Yoshida, Yuichi 2 2017 Parameterized property testing of functions. Zbl 1427.68129 Pallavoor, Ramesh Krishnan S.; Raskhodnikova, Sofya; Varma, Nithin 2 2017 An \(O(n^{\epsilon})\) space and polynomial time algorithm for reachability in directed layered planar graphs. Zbl 1427.68232 Chakraborty, Diptarka; Tewari, Raghunath 2 2017 Lower bounds for constant query affine-invariant LCCs and LTCs. Zbl 1427.94088 Bhattacharyya, Arnab; Gopi, Sivakanth 1 2017 Canonizing graphs of bounded tree width in logspace. Zbl 1427.68238 Elberfeld, Michael; Schweitzer, Pascal 1 2017 Complexity hierarchies beyond elementary. Zbl 1347.68162 Schmitz, Sylvain 33 2016 Characterizing arithmetic read-once formulae. Zbl 1347.68148 Volkovich, Ilya 8 2016 On sample-based testers. Zbl 1427.68360 Goldreich, Oded; Ron, Dana 7 2016 Counting homomorphisms to square-free graphs, modulo 2. Zbl 1427.68241 Göbel, Andreas; Goldberg, Leslie Ann; Richerby, David 5 2016 A Galois connection for weighted (relational) clones of infinite size. Zbl 1427.68120 Fulla, Peter; Živný, Stanislav 4 2016 Parameterized complexity and kernelizability of max ones and exact ones problems. Zbl 1347.68183 Kratsch, Stefan; Marx, Dániel; Wahlström, Magnus 3 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 2 2016 Tractable parameterizations for the minimum linear arrangement problem. Zbl 1427.68118 Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances; Shachnai, Hadas 2 2016 The list-decoding size of Fourier-sparse Boolean functions. Zbl 1427.68362 Haviv, Ishay; Regev, Oded 2 2016 The power of an example: hidden set size approximation using group queries and conditional sampling. Zbl 1427.68221 Ron, Dana; Tsur, Gilad 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 Quadratic maps are hard to sample. Zbl 1427.68109 Viola, Emanuele 2 2016 On hardness of multilinearization and VNP-completeness in characteristic 2. Zbl 1427.68107 Hrubeš, P. 1 2016 Relative discrepancy does not separate information and communication complexity. Zbl 1427.68082 Fontes, Lila; Jain, Rahul; Kerenidis, Iordanis; Laplante, Sophie; Laurière, Mathieu; Roland, Jérémie 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 13 2015 Quantum XOR games. Zbl 1348.81177 Regev, Oded; Vidick, Thomas 12 2015 Some hard families of parameterized counting problems. Zbl 1348.68066 Jerrum, Mark; Meeks, Kitty 10 2015 Mutual dimension. Zbl 1348.03041 Case, Adam; Lutz, Jack H. 8 2015 The fine classification of conjunctive queries and parameterized logarithmic space. Zbl 1347.68179 Chen, Hubie; Müller, Moritz 5 2015 On approximate decidability of minimal programs. Zbl 1347.68096 Teutsch, Jason; Zimand, Marius 2 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 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 ...and 57 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 1,195 Authors 18 Saurabh, Saket 14 Živný, Stanislav 12 Pilipczuk, Marcin L. 11 Gur, Tom 11 Jansen, Bart M. P. 10 Beyersdorff, Olaf 10 Pilipczuk, Michał 8 Datta, Samir 8 Lutz, Neil 8 Raghavendra Rao, B. V. 7 Allender, Eric W. 7 Goldberg, Leslie Ann 7 Lokshtanov, Daniel 7 Marx, Dániel 7 Roth, Marc 7 Sau, Ignasi 7 Tale, Prafullkumar 6 Chen, Hubie 6 Göös, Mika 6 Jansen, Klaus 6 Krokhin, Andrei A. 6 Panolan, Fahad 6 Pieterse, Astrid 6 Schmitt, Johannes 6 Steinberg, Florian 6 Tewari, Raghunath 6 Watson, Thomas 6 Ziegler, Martin 5 Applebaum, Benny 5 Chiesa, Alessandro 5 Ishai, Yuval 5 Komusiewicz, Christian 5 Kratsch, Stefan 5 Kwan, Matthew 5 Lutz, Jack H. 5 Mahajan, Meena 5 Mansutti, Alessio 5 Misra, Pranabendu 5 Niedermeier, Rolf 5 Palazuelos, Carlos 5 Rau, Malin 5 Rothblum, Ron D. 5 Schmitz, Sylvain 5 Servedio, Rocco A. 5 Stull, Donald M. 5 Van Leeuwen, Erik Jan 5 Vinodchandran, N. Variyam 5 Wahlström, Magnus 5 Zehavi, Meirav 4 Agrawal, Akanksha 4 Blinkhorn, Joshua 4 Bousquet, Nicolas 4 Chitnis, Rajesh Hemant 4 Cygan, Marek 4 Damaschke, Peter 4 Fluschnik, Till 4 Fomin, Fedor V. 4 Froese, Vincent 4 Galanis, Andreas 4 Göbel, Andreas-Nikolas 4 Greco, Gianluigi 4 Guruswami, Venkatesan 4 Hirahara, Shuichi 4 Katoen, Joost-Pieter 4 Kawamura, Akitoshi 4 Lagerkvist, Victor 4 Lazić, Ranko 4 Mayordomo, Elvira 4 Micciancio, Daniele 4 Raman, Venkatesh 4 Tan, Liyang 4 Thaler, Justin 4 Thierauf, Thomas 4 Tu, Jianhua 4 van Bevern, René 4 Viola, Emanuele 4 Wellnitz, Philip 4 Woodruff, David P. 4 Wrochna, Marcin 3 Altman, Harry J. 3 Böhm, Benjamin 3 Brandt, Felix 3 Cai, Jin-Yi 3 Campos, Victor A. 3 Cao, Yixin 3 Case, Adam 3 Chang, Ching-Lueh 3 Chen, Lijie 3 Cheon, Jung Hee 3 Dadush, Daniel 3 Demri, Stéphane P. 3 Drange, Pål Grønås 3 Fischer, Felix 3 Friedrich, Tobias 3 Fu, Zhiguo 3 Gabarró, Joaquim 3 Ghosh, Arijit 3 Gurjar, Rohit 3 Harris, Samuel J. 3 Hatami, Pooya ...and 1,095 more Authors all top 5 Cited in 122 Journals 45 SIAM Journal on Computing 43 Algorithmica 40 Theoretical Computer Science 25 Journal of Computer and System Sciences 25 Computational Complexity 25 Theory of Computing Systems 18 SIAM Journal on Discrete Mathematics 14 Information and Computation 10 Journal of Cryptology 9 Artificial Intelligence 9 Logical Methods in Computer Science 8 Information Processing Letters 6 ACM Transactions on Computational Logic 5 Discrete Applied Mathematics 5 SIAM Journal on Matrix Analysis and Applications 4 Information Sciences 4 Journal of Automated Reasoning 4 Quantum Information Processing 3 Discrete Mathematics 3 Israel Journal of Mathematics 3 Journal of Functional Analysis 3 The Journal of Symbolic Logic 3 Random Structures & Algorithms 3 Mathematical Programming. Series A. Series B 3 Cybernetics and Systems Analysis 3 Journal of Combinatorial Optimization 3 Journal of the ACM 3 Journal of Machine Learning Research (JMLR) 3 Discrete Optimization 3 Theory of Computing 3 Computability 2 Acta Informatica 2 Communications in Mathematical Physics 2 Journal of Mathematical Analysis and Applications 2 Journal of Mathematical Physics 2 Mathematical Proceedings of the Cambridge Philosophical Society 2 Journal of Combinatorial Theory. Series B 2 Mathematics of Operations Research 2 Combinatorica 2 Annals of Pure and Applied Logic 2 Journal of Symbolic Computation 2 Journal of Complexity 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 Designs, Codes and Cryptography 2 The Journal of Artificial Intelligence Research (JAIR) 2 Constraints 2 Journal of Discrete Algorithms 2 Journal of Mathematical Cryptology 2 Foundations and Trends in Theoretical Computer Science 2 ACM Transactions on Algorithms 2 Forum of Mathematics, Pi 2 Computer Science Review 2 Discrete Analysis 1 International Journal of Theoretical Physics 1 Journal of Statistical Physics 1 Advances in Mathematics 1 The Annals of Probability 1 The Annals of Statistics 1 Applied Mathematics and Computation 1 Journal of Algebra 1 Journal of Graph Theory 1 Journal of the Korean Mathematical Society 1 Journal of the London Mathematical Society. Second Series 1 Journal of Pure and Applied Algebra 1 Operations Research 1 Transactions of the American Mathematical Society 1 European Journal of Combinatorics 1 Operations Research Letters 1 Probability Theory and Related Fields 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 European Journal of Operational Research 1 Distributed Computing 1 The Australasian Journal of Combinatorics 1 New Zealand Journal of Mathematics 1 Journal of Applied Non-Classical Logics 1 Combinatorics, Probability and Computing 1 Mathematical Logic Quarterly (MLQ) 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 Bernoulli 1 INFORMS Journal on Computing 1 Mathematical Problems in Engineering 1 Soft Computing 1 Journal of Scheduling 1 Annals of Combinatorics 1 Discrete Mathematics and Theoretical Computer Science. DMTCS 1 International Journal of Applied Mathematics and Computer Science ...and 22 more Journals all top 5 Cited in 35 Fields 531 Computer science (68-XX) 147 Combinatorics (05-XX) 96 Information and communication theory, circuits (94-XX) 66 Mathematical logic and foundations (03-XX) 58 Operations research, mathematical programming (90-XX) 37 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 21 Quantum theory (81-XX) 15 Statistics (62-XX) 14 General algebraic systems (08-XX) 14 Number theory (11-XX) 12 Measure and integration (28-XX) 12 Probability theory and stochastic processes (60-XX) 12 Numerical analysis (65-XX) 10 Functional analysis (46-XX) 9 Linear and multilinear algebra; matrix theory (15-XX) 8 Order, lattices, ordered algebraic structures (06-XX) 7 Statistical mechanics, structure of matter (82-XX) 6 Commutative algebra (13-XX) 6 Group theory and generalizations (20-XX) 5 Operator theory (47-XX) 5 Convex and discrete geometry (52-XX) 4 Algebraic geometry (14-XX) 4 Harmonic analysis on Euclidean spaces (42-XX) 3 Field theory and polynomials (12-XX) 3 Biology and other natural sciences (92-XX) 2 Functions of a complex variable (30-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 General topology (54-XX) 2 Systems theory; control (93-XX) 1 General and overarching topics; collections (00-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-XX) 1 Algebraic topology (55-XX) 1 Mechanics of particles and systems (70-XX) 1 Fluid mechanics (76-XX) Citations by Year