ACM DL

ACM Transactions on

Computation Theory (TOCT)

Menu
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)

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.

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.

Bibliometrics

Publication Years 2009-2017
Publication Count 113
Citation Count 194
Available for Download 113
Downloads (6 weeks) 232
Downloads (12 Months) 2756
Downloads (cumulative) 25171
Average downloads per article 223
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
Toniann Pitassi 4
Leslie Goldberg 4
Meena Mahajan 4
Stephen Cook 4
Dana Ron 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
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
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
Yi Wu 1
Mihalis Yannakakis 1
Ilya Volkovich 1
Nir Ailon 1
Dániel Marx 1
Francesco Scarcello 1
Frances Rosamond 1
Akitoshi Kawamura 1
Rahul Jain 1
Iordanis Kerenidis 1
Sophie Laplante 1
Víctor Dalmau 1
Elchanan Mossel 1
Venkatesh Raman 1
Saurabh Sawlani 1
Hubie Chen 1
CLIFFORD Smyth 1
Gido Scharfenberger-Fabian 1
David Barber 1
Jan Kynčl 1
Matei David 1
Michal Koucký 1
Prahladh Harsha 1
Andrej Bogdanov 1
Kousha Etessami 1
Alistair Stewart 1
Paul Valiant 1
Seiichiro Tani 1
Gianluigi Greco 1
Saket Saurabh 1
Nathan Grosshans 1
Anil Ada 1
Ryan Harkins 1
Fabian Wagner 1
Andreas Galanis 1
Anant Dhayal 1
Arnab Bhattacharyya 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
Magnus Wahlström 1
Nicola Galesi 1
Bart Jansen 1
Daitri 1
Mrinal Kumar 1
Andrei Krokhin 1
Sivakanth Gopi 1
Varun Kanade 1
James Cook 1
Hirotada Kobayashi 1
Carmine Ventre 1
Salil Vadhan 1
Marco Molinaro 1
Enrico Malizia 1
Daniel Lokshtanov 1
Ishay Haviv 1
Luc Segoufin 1
Ronen Shaltiel 1
Yi Wu 1
Christos Kaklamanis 1
Simon Straub 1
Danny Hermelin 1
Kitty Meeks 1
Andris Ambainis 1
Chris Bourke 1
Andrew Mills 1
Martin Hoefer 1
Prasad Raghavendra 1
Russell Impagliazzo 1
John Wright 1
Stephen Travers 1
Heiko Röglin 1
Hidetoki Tanaka 1
Rachel Miller 1
Craig Gentry 1
Vinod Vaikuntanathan 1
Luca Trevisan 1
Keiji Matsumoto 1
Mahdi Cheraghchi 1
Elena Losievskaja 1
Rasmus Pagh 1
Stanislav Živný 1
Alan Selman 1
Marius Zimand 1
Yngve Villanger 1
Alejandro López-Ortíz 1
Muli Safra 1
Rafael Pass 1
Andrey Utis 1
Heribert Vollmer 1
Michael Littman 1
Yitong Yin 1
Tomáš Vyskočil 1
Balagopal Komarath 1
Markus Bläser 1
Yonatan Goldhirsh 1
Vikraman Arvind 1
Hannes Moser 1
Rolf Niedermeier 1
Muthuramakrishnan Venkitasubramaniam 1
Raghunath Tewari 1
Jack Lutz 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
Michael Viderman 1
Andrew Drucker 1
S Raja 1
Jingtang Jang 1
Jazmin Romero 1
Neeraj Kayal 1
Jiong Guo 1
Omri Weinstein 1
Lance Fortnow 1
Mark Braverman 1
Venkatesan Guruswami 1
Eli Ben-Sasson 1
Arie Matsliah 1
Akinori Kawachi 1
Paolo Penna 1
Madhav Jha 1
Sofya Raskhodnikova 1
Peter Fulla 1
Pavel Hrubeš 1
Grant Schoenebeck 1
Dung Nguyen 1
Mathieu Laurière 1
Sergei Artemenko 1
Pål Drange 1
Ioannis Caragiannis 1
Chandan Saha 1
William Gasarch 1
Michael Thomas 1
Scott Aaronson 1
Avi Wigderson 1
Adam Case 1
Trinh Huynh 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
Aravind Srinivasan 1
Nikos Vlassis 1
Yijia Chen 1
Ning Zhong 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