ACM Transactions on

Computation Theory (TOCT)

Latest Articles

Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits

A sampling procedure for a distribution P over {0, 1}ℓ is a function C: {0, 1}n → {0, 1}ℓ such that... (more)

Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the... (more)

Exact Perfect Matching in Complete Graphs

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges. We show that for complete and bipartite complete graphs, the exact perfect matching problem is logspace equivalent to the perfect matching... (more)

A Complexity Trichotomy for Approximately Counting List H-Colorings

We examine the computational complexity of approximately counting the list H-colorings of a graph. We discover a natural graph-theoretic trichotomy... (more)

Min/Max-Poly Weighting Schemes and the NL versus UL Problem

For a graph G(V, E) (|V| = n) and a vertex s ∈ V, a weighting scheme (W : E ↦ Z+) is called a min-unique (resp.... (more)



New ACM ToCT Editor-in-Chief

Venkatesan Guruswami is the new Editor-in-Chief for ACM ToCT, as of February 1, 2017

About TOCT

The ACM Transactions on Computation Theory (TOCT) is a peer-reviewed journal that explores the mathematical nature of computation and it's theoretical limitations (with an emphasis on computational complexity, foundations of cryptography and other computation-based topics in theoretical computer science).

read more
Forthcoming Articles
Finding Consensus Strings With Small Length Difference Between Input and Solution Strings

The Closest Substring Problem is to decide, for given strings s_1, ..., s_k of length at most p and numbers m and d, whether there is a length-m string s and length-m substrings s'_i of s_i, such that s has a hamming distance of at most d from each s'_i. If we instead require the sum of all the hamming distances between s and each s'_i to be bounded by d, then it is called the Consensus Patterns Problem. We contribute to the parameterised complexity analysis of these classical NP-hard string problems by investigating the parameter (p - m), i.e., the length difference between input and solution strings. For most combinations of (p - m) and one of the classical parameters (m, p, k or d), we obtain fixed-parameter tractability. However, even for constant (p - m) and constant alphabet size, both problems remain NP-hard. While this follows from known results with respect to the Closest Substring Problem, we need a new reduction in the case of the Consensus Patterns Problem. As a by-product of this reduction, we obtain an exact exponential-time algorithm for both problems, which is based on an alphabet reduction.

Hardness of approximation for strip packing

Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing. The problem has multiple applications, e.g. in scheduling and stock-cutting, and has been studied extensively.

When the dimensions of objects are allowed to be exponential in the total input size, it is known that the problem cannot be approximated within a factor better than $3/2$, unless $\mathrm{P}=\mathrm{NP}$. However, there was no corresponding lower bound for polynomially bounded input data. In fact, Nadiradze and Wiese [SODA 2016] have recently proposed a $(1.4 + \epsilon)$ approximation algorithm for this variant, thus showing that strip packing with polynomially bounded data can be approximated better than when exponentially large values in the input data are allowed. Their result has subsequently been improved to a $(4/3 + \epsilon)$ approximation by two independent research groups [FSTTCS 2016, arXiv:1610.04430]. This raises a question whether strip packing with polynomially bounded input data admits a quasi-polynomial time approximation scheme, as is the case for related two-dimensional packing problems like maximum independent set of rectangles or two-dimensional knapsack.

In this paper we answer this question in negative by proving that it is NP-hard to approximate strip packing within a factor better than $12/11$, even when admitting only polynomially bounded input data. In particular, this shows that the strip packing problem admits no quasi-polynomial time approximation scheme, unless $\mathrm{NP} \subseteq \mathrm{DTIME}(2^{\mathrm{polylog}(n)})$.

The Complexity of Approximately Counting Tree Homomorphisms

We study two computational problems, parameterised by a fixed tree H. #HomsTo(H) is the problem of counting homomorphisms from an input graph G to H. #WHomsTo(H) is the problem of counting weighted homomorphisms to H, given an input graph G and a weight function for each vertex v of G. Even though H is a tree, these problems turn out to be sufficiently rich to capture all of the known approximation behaviour in #P. We give a complete trichotomy for #WHomsTo(H). If H is a star then #WHomsTo(H)$ is in FP. If H is not a star but it does not contain a certain induced subgraph J_3 then #WHomsTo(H) is equivalent under approximation-preserving (AP) reductions to #BIS, the problem of counting independent sets in a bipartite graph. This problem is complete for the class #RHPi_1 under AP-reductions. Finally, if H contains an induced J_3 then #WHomsTo(H)$ is equivalent under AP-reductions to #SAT, the problem of counting satisfying assignments to a CNF Boolean formula. Thus, #WHomsTo(H) is complete for #P under AP-reductions. The results are similar for #HomsTo(H) except that a rich structure emerges if H contains an induced J_3. We show that there are trees H for which #HomsTo(H) is #SAT-equivalent (disproving a plausible conjecture of Kelk). There is an interesting connection between these homomorphism-counting problems and the problem of approximating the partition function of the ferromagnetic Potts model. In particular, we show that for a family of graphs J_q, parameterised by a positive integer q, the problem #HomsTo(H) is AP-interreducible with the problem of approximating the partition function of the q-state Potts model. It was not previously known that the Potts model had a homomorphism-counting interpretation. We use this connection to obtain some additional upper bounds for the approximation complexity of #HomsTo(J_q).

Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

We present and study a framework in which
one can present alternation-based lower bounds
on proof length in proof systems for quantified Boolean formulas.
A key notion in this framework is that of
proof system ensemble, which is
(essentially) a sequence of proof systems
where, for each, proof checking can be performed in
the polynomial hierarchy.
We introduce a proof system ensemble
called relaxing QU-res which is based on the
established proof system QU-resolution.
Our main results include an exponential separation of
the tree-like and general versions of relaxing QU-res,
and an exponential lower bound for relaxing QU-res;
these are analogs of
classical results in propositional proof complexity.


Publication Years 2009-2017
Publication Count 113
Citation Count 172
Available for Download 113
Downloads (6 weeks) 355
Downloads (12 Months) 2899
Downloads (cumulative) 19310
Average downloads per article 171
Average citations per article 2
First Name Last Name Award
Mahdi Cheraghchi ACM Senior Member (2016)
Stephen A Cook ACM A. M. Turing Award (1982)
Craig Gentry ACM Grace Murray Hopper Award (2010)
ACM Doctoral Dissertation Award (2009)
Rohit Gurjar ACM India Doctoral Dissertation Award (2017)
Venkatesan Guruswami ACM Doctoral Dissertation Award (2002)
Johan Torkel Hastad ACM Doctoral Dissertation Award (1986)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)

First Name Last Name Paper Counts
Leslie Goldberg 4
Toniann Pitassi 4
Stephen Cook 4
Meena Mahajan 4
Dana Ron 4
John Hitchcock 3
Ryan O’Donnell 3
Nutan Limaye 3
Emanuele Viola 3
Paul Beame 3
Thomas Watson 3
Stefan Kratsch 3
Karteek Sreenivasaiah 3
Jayalal Sarma 3
Alexander Razborov 3
Marcin Pilipczuk 3
Michał Pilipczuk 3
Per Austrin 2
Lila Fontes 2
Michael Fellows 2
Samir Datta 2
Andreas Krebs 2
N Vinodchandran 2
Jérémie Roland 2
Yuval Filmus 2
Jochen Messner 2
Johan Håstad 2
Yuan Zhou 2
Rahul Santhanam 2
Arpita Korwar 2
Anindya De 2
David Richerby 2
Pierre McKenzie 2
Andreas Göbel 2
A Pavan 2
Oded Lachish 2
Rohit Gurjar 2
Gilad Tsur 2
Anna Gál 2
Oded Goldreich 2
Moritz Müller 2
Thomas Thierauf 2
Raghav Kulkarni 2
Olaf Beyersdorff 2
Massimo Lauria 2
Michael Fellows 2
Arkadev Chattopadhyay 2
Oded Regev 2
Marek Cygan 2
Fedor Fomin 2
Jacobo Torán 2
Mark Jerrum 2
Balagopal Komarath 1
Markus Bläser 1
Yonatan Goldhirsh 1
Vikraman Arvind 1
Hannes Moser 1
Rolf Niedermeier 1
Muthuramakrishnan Venkitasubramaniam 1
Jack Lutz 1
Jakub Wojtaszczyk 1
Raghunath Tewari 1
Christian Glaßer 1
Jacob Sponemann 1
Berthold Vöcking 1
Ryan Williams 1
Magnus Wahlström 1
S Raja 1
Mark Jerrum 1
Shafi Goldwasser 1
Sylvain Schmitz 1
Marcus Isaksson 1
Māris Ozols 1
Martin Roetteler 1
Michael Viderman 1
Andrew Drucker 1
Jingtang Jang 1
Neeraj Kayal 1
Omri Weinstein 1
Jazmin Romero 1
Jiong Guo 1
Lance Fortnow 1
Mark Braverman 1
Venkatesan Guruswami 1
Eli Ben-Sasson 1
Arie Matsliah 1
Akinori Kawachi 1
Madhav Jha 1
Sofya Raskhodnikova 1
Dung Nguyen 1
Pavel Hrubeš 1
Peter Fulla 1
Mathieu Laurière 1
Paolo Penna 1
Grant Schoenebeck 1
Sergei Artemenko 1
Pål Drange 1
Ioannis Caragiannis 1
Chandan Saha 1
Michael Thomas 1
William Gasarch 1
Adam Case 1
Scott Aaronson 1
Avi Wigderson 1
Trinh Huynh 1
Nathan Segerlind 1
Matthias Englert 1
Omid Etesami 1
Pranjal Awasthi 1
Pushkar Joglekar 1
Zvika Brakerski 1
Eric Allender 1
Ola Svensson 1
Luigi Palopoli 1
Gaurav Maheshwari 1
Vikraman Arvind 1
Thomas Steinke 1
Ashutosh Rai 1
Jason Teutsch 1
Or Meir 1
Maria Kyropoulou 1
Hadas Shachnai 1
Frances Rosamond 1
Eldar Fischer 1
Ronitt Rubinfeld 1
Alex Samorodnitsky 1
Nikos Vlassis 1
Aravind Srinivasan 1
Yijia Chen 1
James Cook 1
Marco Molinaro 1
Luc Segoufin 1
Ning Zhong 1
Hirotada Kobayashi 1
Enrico Malizia 1
Ishay Haviv 1
Daniel Lokshtanov 1
Salil Vadhan 1
Carmine Ventre 1
Varun Kanade 1
Ronen Shaltiel 1
Marius Zimand 1
Yi Wu 1
Christos Kaklamanis 1
Simon Straub 1
Danny Hermelin 1
Kitty Meeks 1
Andris Ambainis 1
Chris Bourke 1
Martin Hoefer 1
Andrew Mills 1
Russell Impagliazzo 1
Prasad Raghavendra 1
John Wright 1
Stephen Travers 1
Heiko Röglin 1
Hidetoki Tanaka 1
Rachel Miller 1
Luca Trevisan 1
Rasmus Pagh 1
Alan Selman 1
Craig Gentry 1
Vinod Vaikuntanathan 1
Keiji Matsumoto 1
Mahdi Cheraghchi 1
Stanislav Živný 1
Elena Losievskaja 1
Yngve Villanger 1
Muli Safra 1
Alejandro López-Ortíz 1
Rafael Pass 1
Michael Littman 1
Heribert Vollmer 1
Andrey Utis 1
Yitong Yin 1
Tomáš Vyskočil 1
Anil Ada 1
Dániel Marx 1
Víctor Dalmau 1
Yi Wu 1
Nir Ailon 1
Ilya Volkovich 1
Francesco Scarcello 1
Rahul Jain 1
Iordanis Kerenidis 1
Sophie Laplante 1
Elchanan Mossel 1
Frances Rosamond 1
Akitoshi Kawamura 1
Mihalis Yannakakis 1
Venkatesh Raman 1
Saurabh Sawlani 1
Hubie Chen 1
Clifford Smyth 1
David Barber 1
Gido Scharfenberger-Fabian 1
Jan Kynčl 1
Matei David 1
Prahladh Harsha 1
Michal Koucký 1
Andrej Bogdanov 1
Paul Valiant 1
Seiichiro Tani 1
Gianluigi Greco 1
Nathan Grosshans 1
Ryan Harkins 1
Fabian Wagner 1
Saket Saurabh 1
Kousha Etessami 1
Alistair Stewart 1
Arnab Bhattacharyya 1
Andreas Galanis 1
Anant Dhayal 1
Bodo Manthey 1
Thomas Vidick 1
Henning Fernau 1
Eric Purdy 1
Alexander Souza 1
Dustin Wehr 1
Liyang Tan 1
Jörg Flum 1
Magnus Wahlström 1
Bart Jansen 1
Daitri 1
Andrei Krokhin 1
Shuming Sun 1
Nicola Galesi 1
Mrinal Kumar 1
Sivakanth Gopi 1

Affiliation Paper Counts
Universite Libre de Bruxelles 1
Ecole Normale Superieure 1
Humboldt University of Berlin 1
Chalmers University of Technology 1
McGill University 1
Chinese University of Hong Kong 1
Towson University 1
Ecole Normale Superieure de Cachan 1
MIT Computer Science and Artificial Intelligence Laboratory 1
University of Salerno 1
Northwestern University 1
University of Bonn 1
Universitat Politecnica de Catalunya 1
Cornell University 1
Hebrew University of Jerusalem 1
Birkbeck University of London 1
IBM Research 1
Center for Mathematics and Computer Science - Amsterdam 1
Technical University of Berlin 1
University of Trier 1
University of Leeds 1
Stanford University 1
Indian Institute of Science 1
The University of North Carolina at Greensboro 1
IT University of Copenhagen 1
University of Twente 1
Microsoft Research 1
New York University 1
University College London 1
University of Durham 1
Shanghai Jiaotong University 1
University of Cincinnati 1
University of Tokyo 1
Nippon Telegraph and Telephone Corporation 1
University of Freiburg 1
Virginia Tech 1
University of Rochester 1
Hungarian Academy of Sciences 1
University of the Basque Country 1
Swiss Federal Institute of Technology, Lausanne 1
Friedrich Schiller University Jena 1
University of California, San Diego 1
Academy of Sciences of the Czech Republic (Avcr.Cz) 1
University at Buffalo, State University of New York 1
Universitat Pompeu Fabra 1
Intel Corporation 1
Nanjing University 1
University of Iceland 1
University of Luxembourg 1
Academic College of Tel-Aviv - Yaffo 1
Centre for Quantum Technologies, Singapore 1
Vishwakarma Institute of Technology 1
Specifications and Verification Laboratory 1
Universite Paris Saclay 1
Laboratoire de Recherche en Informatique 1
Pennsylvania State University 2
University of Roma La Sapienza 2
University of Patras 2
Tokyo Institute of Technology 2
Rutgers, The State University of New Jersey 2
Columbia University 2
Ben-Gurion University of the Negev 2
University of Vienna 2
The University of Warwick 2
Indian Institute of Technology, Kanpur 2
Chennai Mathematical Institute 2
NEC Laboratories America, Inc. 2
University of Tubingen 2
Charles University 2
Indian Institute of Technology, Bombay 2
University of Wurzburg 2
Brown University 2
University of Montreal 2
Utrecht University 2
Google Inc. 2
University of Haifa 2
Saarland University 2
Massachusetts Institute of Technology 3
University of Wyoming 3
Gottfried Wilhelm Leibniz Universitat 3
Harvard University 3
University of Texas at Austin 3
Northeastern University 3
University of Maryland 3
Royal Institute of Technology 3
RWTH Aachen University 3
Aalen University of Applied Sciences 3
University of Waterloo 4
University of Nebraska - Lincoln 4
University of Ulm 4
University of Calabria 4
Iowa State University 4
University of Edinburgh 4
Charles Darwin University 4
Queen Mary, University of London 4
Princeton University 4
University of Chicago 5
Max Planck Institute for Informatics 5
Universite Paris 7- Denis Diderot 5
Weizmann Institute of Science Israel 5
Technion - Israel Institute of Technology 6
University of Warsaw 6
University of Washington, Seattle 6
Indian Institute of Technology, Madras 7
Institute of Mathematical Sciences India 7
University of California, Berkeley 8
Tel Aviv University 8
University of Bergen 10
Carnegie Mellon University 11
University of Oxford 12
University of Toronto 19
All ACM Journals | See Full Journal Index

Search TOCT
enter search term and/or author name