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
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 186
Available for Download 113
Downloads (6 weeks) 376
Downloads (12 Months) 2818
Downloads (cumulative) 19493
Average downloads per article 173
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
Dana Ron 4
Toniann Pitassi 4
Leslie Goldberg 4
Stephen Cook 4
Meena Mahajan 4
Alexander Razborov 3
Jayalal Sarma 3
Karteek Sreenivasaiah 3
Stefan Kratsch 3
Thomas Watson 3
John Hitchcock 3
Emanuele Viola 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
Andreas Krebs 2
Samir Datta 2
Michael Fellows 2
Oded Regev 2
Yuval Filmus 2
N Vinodchandran 2
Arpita Korwar 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
Michael Fellows 2
Balagopal Komarath 1
Markus Bläser 1
Vikraman Arvind 1
Yonatan Goldhirsh 1
Hannes Moser 1
Rolf Niedermeier 1
Jack Lutz 1
Jakub Wojtaszczyk 1
Raghunath Tewari 1
Muthuramakrishnan Venkitasubramaniam 1
Christian Glaßer 1
Jacob Sponemann 1
Berthold Vöcking 1
Magnus Wahlström 1
Ryan Williams 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
Jiong Guo 1
Neeraj Kayal 1
Lance Fortnow 1
Omri Weinstein 1
Mark Braverman 1
Eli Ben-Sasson 1
Venkatesan Guruswami 1
Arie Matsliah 1
Akinori Kawachi 1
Madhav Jha 1
Sofya Raskhodnikova 1
Paolo Penna 1
Grant Schoenebeck 1
Dung Nguyen 1
Peter Fulla 1
Pavel Hrubeš 1
Mathieu Laurière 1
Sergei Artemenko 1
Pål Drange 1
Ioannis Caragiannis 1
William Gasarch 1
Michael Thomas 1
Adam Case 1
Chandan Saha 1
Scott Aaronson 1
Avi Wigderson 1
Trinh Huynh 1
Nathan Segerlind 1
Matthias Englert 1
Zvika Brakerski 1
Luigi Palopoli 1
Thomas Steinke 1
Omid Etesami 1
Eric Allender 1
Ola Svensson 1
Pranjal Awasthi 1
Gaurav Maheshwari 1
Ashutosh Rai 1
Vikraman Arvind 1
Pushkar Joglekar 1
Jason Teutsch 1
Or Meir 1
Maria Kyropoulou 1
Frances Rosamond 1
Hadas Shachnai 1
Eldar Fischer 1
Aravind Srinivasan 1
Alex Samorodnitsky 1
Ronitt Rubinfeld 1
Nikos Vlassis 1
Ning Zhong 1
Hirotada Kobayashi 1
Enrico Malizia 1
Yijia Chen 1
Varun Kanade 1
James Cook 1
Marco Molinaro 1
Salil Vadhan 1
Carmine Ventre 1
Ishay Haviv 1
Luc Segoufin 1
Daniel Lokshtanov 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
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
Keiji Matsumoto 1
Mahdi Cheraghchi 1
Rachel Miller 1
Luca Trevisan 1
Rasmus Pagh 1
Alan Selman 1
Stanislav Živný 1
Elena Losievskaja 1
Marius Zimand 1
Yngve Villanger 1
Alejandro López-Ortíz 1
Andrey Utis 1
Heribert Vollmer 1
Rafael Pass 1
Muli Safra 1
Michael Littman 1
Yitong Yin 1
Tomáš Vyskočil 1
Anil Ada 1
Yi Wu 1
Ilya Volkovich 1
Dániel Marx 1
Francesco Scarcello 1
Nir Ailon 1
Mihalis Yannakakis 1
Akitoshi Kawamura 1
Venkatesh Raman 1
Rahul Jain 1
Iordanis Kerenidis 1
Sophie Laplante 1
Frances Rosamond 1
Víctor Dalmau 1
Elchanan Mossel 1
Saurabh Sawlani 1
Hubie Chen 1
CLIFFORD Smyth 1
Gido Scharfenberger-Fabian 1
David Barber 1
Matei David 1
Jan Kynčl 1
Michal Koucký 1
Prahladh Harsha 1
Andrej Bogdanov 1
Paul Valiant 1
Gianluigi Greco 1
Seiichiro Tani 1
Kousha Etessami 1
Alistair Stewart 1
Nathan Grosshans 1
Ryan Harkins 1
Fabian Wagner 1
Saket Saurabh 1
Arnab Bhattacharyya 1
Andreas Galanis 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
Shuming Sun 1
Magnus Wahlström 1
Bart Jansen 1
Daitri 1
Jörg Flum 1
Nicola Galesi 1
Mrinal Kumar 1
Andrei Krokhin 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