ACM Transactions on

Computation Theory (TOCT)

Latest Articles

Asking the Metaquestions in Constraint Tractability

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there... (more)

Canonizing Graphs of Bounded Tree Width in Logspace

Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two... (more)

Finding Consensus Strings with Small Length Difference between Input and Solution Strings

The Closest Substring Problem is to decide, for given strings s1, … , sk of length at most ℓ and numbers m and d, whether there is a... (more)

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, for example, in scheduling and stock-cutting, and has been studied extensively. When the dimensions of the objects are allowed to... (more)

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.... (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

Parameterized Testability

An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for any $\epsilon > 0$. The previous best known space bound for this problem with polynomial time was approximately $O(\sqrt{n})$ space \cite{INPVW13}.

Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.

Parameterized Property Testing of Functions

On space efficiency of algorithms working on structural decompositions of graphs

Dynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition's width. Following the work of Allender et al. [Theory of Computing, 2014], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [J. Comput. Syst. Sci., 2003], we prove that the question is closely related to a conjecture that the Longest Common Subsequence problem parameterized by the number of input strings does not admit an algorithm that simultaneously uses XP time and FPT space.

Moreover, we complete the complexity landscape sketched for pathwidth and treewidth by Allender et al. by considering the parameter tree-depth. We prove that computations on tree-depth decompositions correspond to a model of non-deterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition's depth.
Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomial-time non-deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and tree-depth.

Metric $1$-median selection: Query complexity vs.\ approximation ratio

Consider the problem of finding a point in a metric space $(\{1,2,\ldots,n\},d)$ with the minimum average distance to other points.
We show that this problem has no deterministic $o(n^{1+1/(h-1)})$-query $(2h-\epsilon)$-approximation
algorithms for any constants $h\in\mathbb{Z}^+\setminus\{1\}$ and $\epsilon>0$.
Combining our result with existing ones, we determine the best approximation ratio achievable by deterministic
$O(n^{1+\epsilon})$-query (resp., $O(n^{1+\epsilon})$-time)
algorithms to be $2\lceil1/\epsilon\rceil$, for {\em all} constants $\epsilon\in(0,1)$.


Publication Years 2009-2017
Publication Count 118
Citation Count 198
Available for Download 118
Downloads (6 weeks) 429
Downloads (12 Months) 2811
Downloads (cumulative) 25247
Average downloads per article 214
Average citations per article 2
First Name Last Name Award
Mahdi Cheraghchi ACM Senior Member (2016)
Stephen A Cook ACM Fellows (2008)
ACM A. M. Turing Award (1982)
Lance Fortnow ACM Fellows (2007)
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)
Ronitt Rubinfeld ACM Fellows (2014)
Alan Selman ACM Fellows (1998)
Aravind Srinivasan ACM Fellows (2014)
Johan Torkel Hastad ACM Doctoral Dissertation Award (1986)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)
Mihalis Yannakakis ACM Fellows (1998)

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