ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
Latest Articles

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

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)

NEWS

 

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
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 graphs are isomorphic exactly if their canons are equal. We
show that graphs of bounded tree width can be canonized by logarithmic-space
(logspace) algorithms. This implies that the isomorphism problem for graphs of
bounded tree width can be decided in logspace. In the light of isomorphism for
trees being hard for the complexity class logspace, this makes the ubiquitous
class of graphs of bounded tree width one of the few classes of graphs for which
the complexity of the isomorphism problem has been exactly determined.

Asking the metaquestions in constraint tractability


The \emph{constraint satisfaction problem (CSP)} involves deciding,
given a set of variables and a set of constraints on the
variables, whether or not there is an assignment to the variables satisfying all of the constraints.
One formulation of the CSP is as the problem of deciding,
given a pair $(\bbG, \bbH)$ of relational structures,
whether or not there is a homomorphism from the first structure
to the second structure.
The CSP is in general NP-hard;
a common way to restrict this problem
is to fix the second structure $\bbH$, so that
each structure $\bbH$ gives rise to a problem $\csp(\bbH)$.
The problem family $\csp(\bbH)$ has been studied
using an algebraic approach, which links the algorithmic and
complexity properties of each problem $\csp(\bbH)$
to a set of operations, the so-called \emph{polymorphisms}
of $\bbH$.
Certain types of polymorphisms are known to imply the
polynomial-time tractability of $\csp(\bbH)$, and
others are conjectured to do so.
This article systematically studies---for various classes
of polymorphisms---the computational complexity
of deciding whether or not a given structure $\bbH$
admits a polymorphism from the class. Among other results, we prove
the NP-completeness of deciding a condition conjectured
to characterize the tractable problems $\csp(\bbH)$,
as well as the NP-completeness of deciding
if $\csp(\bbH)$ has bounded width.

Bibliometrics

Publication Years 2009-2017
Publication Count 116
Citation Count 196
Available for Download 116
Downloads (6 weeks) 313
Downloads (12 Months) 2863
Downloads (cumulative) 19914
Average downloads per article 172
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
Stephen Cook 4
Leslie Goldberg 4
Meena Mahajan 4
Dana Ron 4
Toniann Pitassi 4
Alexander Razborov 3
Jayalal Sarma 3
Karteek Sreenivasaiah 3
Stefan Kratsch 3
Thomas Watson 3
Emanuele Viola 3
John Hitchcock 3
Marcin Pilipczuk 3
Paul Beame 3
Ryan O’Donnell 3
Nutan Limaye 3
Michał Pilipczuk 3
Moritz Müller 2
Olaf Beyersdorff 2
Massimo Lauria 2
Arkadev Chattopadhyay 2
Marek Cygan 2
Jacobo Torán 2
Raghav Kulkarni 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
Mark Jerrum 2
Jérémie Roland 2
Samir Datta 2
Andreas Krebs 2
Michael Fellows 2
Oded Regev 2
Yuval Filmus 2
N Vinodchandran 2
Arpita Korwar 2
Lila Fontes 2
Per Austrin 2
A Pavan 2
Oded Lachish 2
Rohit Gurjar 2
Gilad Tsur 2
Anna Gál 2
Oded Goldreich 2
Michael Fellows 2
Daniel Lokshtanov 1
Ronen Shaltiel 1
Ning Zhong 1
Luc Segoufin 1
Salil Vadhan 1
Carmine Ventre 1
Yi Wu 1
Christos Kaklamanis 1
Simon Straub 1
Danny Hermelin 1
Kitty Meeks 1
Chris Bourke 1
Andrew Mills 1
Andris Ambainis 1
Martin Hoefer 1
Russell Impagliazzo 1
Prasad Raghavendra 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
Mahdi Cheraghchi 1
Rasmus Pagh 1
Stanislav Živný 1
Alan Selman 1
Elena Losievskaja 1
Marius Zimand 1
Yngve Villanger 1
Alejandro López-Ortíz 1
Muli Safra 1
Michael Littman 1
Rafael Pass 1
Andrey Utis 1
Heribert Vollmer 1
Yitong Yin 1
Tomáš Vyskočil 1
Anil Ada 1
Yi Wu 1
Mihalis Yannakakis 1
Nir Ailon 1
Francesco Scarcello 1
Rahul Jain 1
Iordanis Kerenidis 1
Sophie Laplante 1
Víctor Dalmau 1
Elchanan Mossel 1
Frances Rosamond 1
Ilya Volkovich 1
Dániel Marx 1
Akitoshi Kawamura 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
Kousha Etessami 1
Alistair Stewart 1
Paul Valiant 1
Seiichiro Tani 1
Gianluigi Greco 1
Ryan Harkins 1
Fabian Wagner 1
Saket Saurabh 1
Nathan Grosshans 1
Arnab Bhattacharyya 1
Anant Dhayal 1
Andreas Galanis 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
Nicola Galesi 1
Bart Jansen 1
Daitri 1
Mrinal Kumar 1
Andrei Krokhin 1
Shuming Sun 1
Magnus Wahlström 1
Sivakanth Gopi 1
Balagopal Komarath 1
Markus Bläser 1
Yonatan Goldhirsh 1
Jack Lutz 1
Vikraman Arvind 1
Hannes Moser 1
Rolf Niedermeier 1
Raghunath Tewari 1
Muthuramakrishnan Venkitasubramaniam 1
Jakub Wojtaszczyk 1
Christian Glaßer 1
Jacob Sponemann 1
Berthold Vöcking 1
Ryan Williams 1
Magnus Wahlström 1
Mark Jerrum 1
Shafi Goldwasser 1
Sylvain Schmitz 1
Marcus Isaksson 1
Māris Ozols 1
Martin Roetteler 1
S Raja 1
Michael Viderman 1
Andrew Drucker 1
Jingtang Jang 1
Jazmin Romero 1
Jiong Guo 1
Lance Fortnow 1
Neeraj Kayal 1
Omri Weinstein 1
Mark Braverman 1
Venkatesan Guruswami 1
Eli Ben-Sasson 1
Arie Matsliah 1
Akinori Kawachi 1
Madhav Jha 1
Sofya Raskhodnikova 1
Peter Fulla 1
Dung Nguyen 1
Pavel Hrubeš 1
Mathieu Laurière 1
Sergei Artemenko 1
Grant Schoenebeck 1
Paolo Penna 1
Pål Drange 1
Ioannis Caragiannis 1
Adam Case 1
Scott Aaronson 1
Avi Wigderson 1
Chandan Saha 1
Trinh Huynh 1
William Gasarch 1
Michael Thomas 1
Nathan Segerlind 1
Matthias Englert 1
Thomas Steinke 1
Zvika Brakerski 1
Omid Etesami 1
Eric Allender 1
Ola Svensson 1
Pranjal Awasthi 1
Luigi Palopoli 1
Gaurav Maheshwari 1
Vikraman Arvind 1
Pushkar Joglekar 1
Ashutosh Rai 1
Jason Teutsch 1
Or Meir 1
Maria Kyropoulou 1
Frances Rosamond 1
Hadas Shachnai 1
Eldar Fischer 1
Ronitt Rubinfeld 1
Alex Samorodnitsky 1
Nikos Vlassis 1
Aravind Srinivasan 1
Yijia Chen 1
Varun Kanade 1
James Cook 1
Hirotada Kobayashi 1
Marco Molinaro 1
Enrico Malizia 1
Ishay Haviv 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