Table of contents for issues of ACM Transactions on Computation Theory

Last update: Wed Oct 17 17:45:51 MDT 2018                Valid HTML 3.2!

Volume 1, Number 1, February, 2009
Volume 1, Number 2, September, 2009
Volume 1, Number 3, March, 2010
Volume 2, Number 1, November, 2010
Volume 2, Number 2, March, 2011
Volume 3, Number 1, August, 2011
Volume 3, Number 2, January, 2012
Volume 4, Number 1, March, 2012
Volume 4, Number 2, May, 2012
Volume 4, Number 3, September, 2012
Volume 4, Number 4, November, 2012
Volume 5, Number 1, May, 2013
Volume 5, Number 2, July, 2013
Volume 5, Number 3, August, 2013
Volume 5, Number 4, November, 2013
Volume 6, Number 1, March, 2014
Volume 6, Number 2, May, 2014
Volume 6, Number 3, July, 2014
Volume 6, Number 4, August, 2014
Volume 7, Number 1, December, 2014
Volume 7, Number 2, May, 2015
Volume 7, Number 3, July, 2015
Volume 7, Number 4, September, 2015
Volume 8, Number 1, February, 2016
Volume 8, Number 2, May, 2016
Volume 8, Number 3, May, 2016
Volume 8, Number 4, July, 2016
Volume 9, Number 1, December, 2016
Volume 9, Number 2, May, 2017
Volume 9, Number 3, October, 2017
Volume 9, Number 4, January, 2018
Volume 10, Number 1, January, 2018
Volume 10, Number 2, May, 2018
Volume 10, Number 3, June, 2018
Volume 10, Number 4, October, 2018


ACM Transactions on Computation Theory
Volume 1, Number 1, February, 2009

                  Lance Fortnow   Editor's Foreword  . . . . . . . . . . . 1:1--1:??
             Scott Aaronson and   
                  Avi Wigderson   Algebrization: a New Barrier in
                                  Complexity Theory  . . . . . . . . . . . 2:1--2:??
             Alexander Razborov   A Simple Proof of Bazzi's Theorem  . . . 3:1--3:??
               Chris Bourke and   
           Raghunath Tewari and   
            N. V. Vinodchandran   Directed Planar Reachability Is in
                                  Unambiguous Log-Space  . . . . . . . . . 4:1--4:??

ACM Transactions on Computation Theory
Volume 1, Number 2, September, 2009

                Matei David and   
            Toniann Pitassi and   
                 Emanuele Viola   Improved Separations between
                                  Nondeterministic and Randomized
                                  Multiparty Communication . . . . . . . . 5:1--5:??
       Venkatesan Guruswami and   
             Prasad Raghavendra   Hardness of Solving Sparse
                                  Overdetermined Linear Systems: a 3-Query
                                  PCP over Integers  . . . . . . . . . . . 6:1--6:??
             Eli Ben-Sasson and   
            Prahladh Harsha and   
               Oded Lachish and   
                  Arie Matsliah   Sound 3-Query PCPPs Are Long . . . . . . 7:1--7:??

ACM Transactions on Computation Theory
Volume 1, Number 3, March, 2010

                Jan Kyn\vcl and   
      Tomá\vs Vysko\vcil   Logspace Reduction of Directed
                                  Reachability for Bounded Genus Graphs to
                                  the Planar Case  . . . . . . . . . . . . 8:1--8:??
                 Paul Beame and   
        Russell Impagliazzo and   
            Toniann Pitassi and   
               Nathan Segerlind   Formula Caching in DPLL  . . . . . . . . 9:1--9:??
                Samir Datta and   
            Raghav Kulkarni and   
               Nutan Limaye and   
                  Meena Mahajan   Planarity, Determinants, Permanents, and
                                  (Unique) Matchings . . . . . . . . . . . 10:1--10:??


ACM Transactions on Computation Theory
Volume 2, Number 1, November, 2010

                     Yitong Yin   Cell-Probe Proofs  . . . . . . . . . . . 1:1--1:??
              Martin Hoefer and   
                Alexander Souza   Tradeoffs and Average-Case Equilibria in
                                  Selfish Routing  . . . . . . . . . . . . 2:1--2:??

ACM Transactions on Computation Theory
Volume 2, Number 2, March, 2011

                     Eric Purdy   Lower Bounds for Coin-Weighing Problems  3:1--3:??
            Vikraman Arvind and   
            Jacobo Torán   Solvable Group Isomorphism Is (Almost)
                                  in NP $\cap$ coNP  . . . . . . . . . . . 4:1--4:??
         Michael R. Fellows and   
                  Jiong Guo and   
               Hannes Moser and   
               Rolf Niedermeier   A Complexity Dichotomy for Finding
                                  Disjoint Solutions of Vertex Deletion
                                  Problems . . . . . . . . . . . . . . . . 5:1--5:??


ACM Transactions on Computation Theory
Volume 3, Number 1, August, 2011

          John M. Hitchcock and   
                   A. Pavan and   
            N. V. Vinodchandran   Kolmogorov Complexity in Randomness
                                  Extraction . . . . . . . . . . . . . . . 1:1--1:??
                Raghav Kulkarni   On the Power of Isolation in Planar
                                  Graphs . . . . . . . . . . . . . . . . . 2:1--2:??
                 Clifford Smyth   Approximate Query Complexity . . . . . . 3:1--3:??

ACM Transactions on Computation Theory
Volume 3, Number 2, January, 2012

               Stephen Cook and   
            Pierre McKenzie and   
                Dustin Wehr and   
             Mark Braverman and   
                Rahul Santhanam   Pebbles and Branching Programs for Tree
                                  Evaluation . . . . . . . . . . . . . . . 4:1--4:??
                   Anna Gal and   
                   Andrew Mills   Three-Query Locally Decodable Codes with
                                  Higher Correctness Require Exponential
                                  Length . . . . . . . . . . . . . . . . . 5:1--5:??
                 Paul Beame and   
                    Trinh Huynh   The Value of Multiple Read\slash Write
                                  Streams for Approximating Frequency
                                  Moments  . . . . . . . . . . . . . . . . 6:1--6:??


ACM Transactions on Computation Theory
Volume 4, Number 1, March, 2012

             Seiichiro Tani and   
         Hirotada Kobayashi and   
                Keiji Matsumoto   Exact Quantum Algorithms for the Leader
                                  Election Problem . . . . . . . . . . . . 1:1--1:??
           Mahdi Cheraghchi and   
         Johan Håstad and   
            Marcus Isaksson and   
                   Ola Svensson   Approximating Linear Threshold
                                  Predicates . . . . . . . . . . . . . . . 2:1--2:??
                 Anindya De and   
                  Thomas Watson   Extractors and Lower Bounds for Locally
                                  Samplable Sources  . . . . . . . . . . . 3:1--3:??

ACM Transactions on Computation Theory
Volume 4, Number 2, May, 2012

       Grant R. Schoenebeck and   
                   Salil Vadhan   The Computational Complexity of Nash
                                  Equilibria in Concisely Represented
                                  Games  . . . . . . . . . . . . . . . . . 4:1--4:??
          Akitoshi Kawamura and   
                   Stephen Cook   Complexity Theory for Operators in
                                  Analysis . . . . . . . . . . . . . . . . 5:1--5:??
                Paolo Penna and   
                 Carmine Ventre   Collusion-Resistant Mechanisms with
                                  Verification Yielding Optimal Solutions  6:1--6:??

ACM Transactions on Computation Theory
Volume 4, Number 3, September, 2012

           Olaf Beyersdorff and   
              Nicola Galesi and   
             Massimo Lauria and   
          Alexander A. Razborov   Parameterized Bounded-Depth Frege Is not
                                  Optimal  . . . . . . . . . . . . . . . . 7:1--7:??
                  Thomas Watson   Relativized Worlds without Worst-Case to
                                  Average-Case Reductions for NP . . . . . 8:1--8:??

ACM Transactions on Computation Theory
Volume 4, Number 4, November, 2012

               Neeraj Kayal and   
                   Chandan Saha   On the Sum of Square Roots of
                                  Polynomials and Related Problems . . . . 9:1--9:??
                Rafael Pass and   
Muthuramakrishnan Venkitasubramaniam   A Parallel Repetition Theorem for
                                  Constant-Round Arthur--Merlin Proofs . . 10:1--10:??
                   Dana Ron and   
           Ronitt Rubinfeld and   
                 Muli Safra and   
         Alex Samorodnitsky and   
                 Omri Weinstein   Approximating the Influence of Monotone
                                  Boolean Functions in $ O(\sqrt n) $
                                  Query Complexity . . . . . . . . . . . . 11:1--11:??
              Nikos Vlassis and   
         Michael L. Littman and   
                   David Barber   On the Computational Complexity of
                                  Stochastic Controller Optimization in
                                  POMDPs . . . . . . . . . . . . . . . . . 12:1--12:??


ACM Transactions on Computation Theory
Volume 5, Number 1, May, 2013

                Per Austrin and   
             Johan Håstad   On the usefulness of predicates  . . . . 1:1--1:??
           Olaf Beyersdorff and   
                Samir Datta and   
              Andreas Krebs and   
              Meena Mahajan and   
 Gido Scharfenberger-Fabian and   
      Karteek Sreenivasaiah and   
             Michael Thomas and   
               Heribert Vollmer   Verifying proofs in constant depth . . . 2:1--2:??
                Marek Cygan and   
           Marcin Pilipczuk and   
           Michal Pilipczuk and   
       Jakub Onufry Wojtaszczyk   On multiway cut parameterized above
                                  lower bounds . . . . . . . . . . . . . . 3:1--3:??

ACM Transactions on Computation Theory
Volume 5, Number 2, July, 2013

           Matthias Englert and   
          Heiko Röglin and   
       Jacob Spönemann and   
          Berthold Vöcking   Economical Caching . . . . . . . . . . . 4:1--4:??
            Andrej Bogdanov and   
            Akinori Kawachi and   
                Hidetoki Tanaka   Hard Functions for Low-Degree
                                  Polynomials over Prime Fields  . . . . . 5:1--5:??
                  Ryan Williams   Alternation-Trading Proofs, Linear
                                  Programming, and Lower Bounds  . . . . . 6:1--6:??
                   Dana Ron and   
                     Gilad Tsur   On Approximating the Number of Relevant
                                  Variables in a Function  . . . . . . . . 7:1--7:??

ACM Transactions on Computation Theory
Volume 5, Number 3, August, 2013

              Eric Allender and   
               Shafi Goldwasser   Introduction to the special issue on
                                  innovations in theoretical computer
                                  science 2012 . . . . . . . . . . . . . . 8:1--8:??
                    Rasmus Pagh   Compressed matrix multiplication . . . . 9:1--9:??
               Michael Viderman   Linear-time decoding of regular expander
                                  codes  . . . . . . . . . . . . . . . . . 10:1--10:??
                Maris Ozols and   
           Martin Roetteler and   
   Jérémie Roland   Quantum rejection sampling . . . . . . . 11:1--11:??
                 Andrew Drucker   High-confidence predictions under
                                  adversarial uncertainty  . . . . . . . . 12:1--12:??

ACM Transactions on Computation Theory
Volume 5, Number 4, November, 2013

      Arkadev Chattopadhyay and   
        Jacobo Torán and   
                  Fabian Wagner   Graph Isomorphism is Not
                                  AC$^0$-Reducible to Group Isomorphism    13:1--13:??
                 Anindya De and   
                Elchanan Mossel   Explicit Optimal Hardness via Gaussian
                                  Stability Results  . . . . . . . . . . . 14:1--14:??
       Víctor Dalmau and   
                 Andrei Krokhin   Robust Satisfiability for CSPs: Hardness
                                  and Algorithmic Results  . . . . . . . . 15:1--15:??
            Michael Fellows and   
             Fedor V. Fomin and   
          Daniel Lokshtanov and   
          Elena Losievskaja and   
           Frances Rosamond and   
                  Saket Saurabh   Distortion is Fixed Parameter Tractable  16:1--16:??
         Alexander Razborov and   
                 Emanuele Viola   Real Advantage . . . . . . . . . . . . . 17:1--17:??
            Ryan C. Harkins and   
              John M. Hitchcock   Exact Learning Algorithms, Betting
                                  Games, and Circuit Lower Bounds  . . . . 18:1--18:??


ACM Transactions on Computation Theory
Volume 6, Number 1, March, 2014

                   Anil Ada and   
      Arkadev Chattopadhyay and   
            Stephen A. Cook and   
                Lila Fontes and   
       Michal Koucký and   
                Toniann Pitassi   The Hardness of Being Private  . . . . . 1:1--1:??
                Per Austrin and   
             Ryan O'Donnell and   
                Li-Yang Tan and   
                    John Wright   New NP-Hardness Results for $3$-Coloring
                                  and $2$-to-$1$ Label Cover . . . . . . . 2:1--2:??
     Christian Glaßer and   
          John M. Hitchcock and   
                   A. Pavan and   
                Stephan Travers   Unions of Disjoint NP-Complete Sets  . . 3:1--3:??
               Shu-Ming Sun and   
                     Ning Zhong   On Effective Convergence of Numerical
                                  Solutions for Differential Equations . . 4:1--4:??
             Ryan O'Donnell and   
                      Yi Wu and   
                      Yuan Zhou   Optimal Lower Bounds for
                                  Locality-Sensitive Hashing (Except When
                                  $q$ is Tiny) . . . . . . . . . . . . . . 5:1--5:??

ACM Transactions on Computation Theory
Volume 6, Number 2, May, 2014

                Marek Cygan and   
             Stefan Kratsch and   
           Marcin Pilipczuk and   
           Michal Pilipczuk and   
          Magnus Wahlström   Clique Cover and Graph Separation: New
                                  Incompressibility Results  . . . . . . . 6:1--6:??
                 Yijia Chen and   
             Jörg Flum and   
             Moritz Müller   Hard Instances of Algorithms and Proof
                                  Systems  . . . . . . . . . . . . . . . . 7:1--7:??
        Leslie Ann Goldberg and   
                    Mark Jerrum   The Complexity of Approximately Counting
                                  Tree Homomorphisms . . . . . . . . . . . 8:1--8:??
            Kousha Etessami and   
           Alistair Stewart and   
             Mihalis Yannakakis   A Note on the Complexity of Comparing
                                  Succinctly Represented Integers, with an
                                  Application to Maximum Probability
                                  Parsing  . . . . . . . . . . . . . . . . 9:1--9:??

ACM Transactions on Computation Theory
Volume 6, Number 3, July, 2014

              Eric Allender and   
               Shafi Goldwasser   Introduction to the Special Issue on
                                  Innovations in Theoretical Computer
                                  Science 2012 --- Part II . . . . . . . . 10:1--10:??
               Varun Kanade and   
                 Thomas Steinke   Learning Hurdles for Sleeping Experts    11:1--11:??
                   Paul Valiant   Evolvability of Real Functions . . . . . 12:1--12:??
            Zvika Brakerski and   
               Craig Gentry and   
           Vinod Vaikuntanathan   (Leveled) Fully Homomorphic Encryption
                                  without Bootstrapping  . . . . . . . . . 13:1--13:??
                 James Cook and   
               Omid Etesami and   
              Rachel Miller and   
                  Luca Trevisan   On the One-Way Function Candidate
                                  Proposed by Goldreich  . . . . . . . . . 14:1--14:??

ACM Transactions on Computation Theory
Volume 6, Number 4, August, 2014

            Stephen A. Cook and   
               Yuval Filmus and   
           Dai Tri Man Lê   The complexity of the comparator circuit
                                  value problem  . . . . . . . . . . . . . 15:1--15:??
         Michael R. Fellows and   
              Bart M. P. Jansen   FPT is characterized by useful
                                  obstruction sets: Connecting algorithms,
                                  kernels, and quasi-orders  . . . . . . . 16:1--16:??
         Andreas Göbel and   
        Leslie Ann Goldberg and   
                 David Richerby   The complexity of counting homomorphisms
                                  to cactus graphs modulo 2  . . . . . . . 17:1--17:??


ACM Transactions on Computation Theory
Volume 7, Number 1, December, 2014

                  Thomas Watson   Advice Lower Bounds for the Dense Model
                                  Theorem  . . . . . . . . . . . . . . . . 1:1--1:??
            Pranjal Awasthi and   
                 Madhav Jha and   
             Marco Molinaro and   
            Sofya Raskhodnikova   Limitations of Local Filters of
                                  Lipschitz and Monotone Functions . . . . 2:1--2:??
            Gianluigi Greco and   
             Enrico Malizia and   
             Luigi Palopoli and   
            Francesco Scarcello   The Complexity of the Nucleolus in
                                  Compact Games  . . . . . . . . . . . . . 3:1--3:??
             Stefan Kratsch and   
           Marcin Pilipczuk and   
               Ashutosh Rai and   
                Venkatesh Raman   Kernel Lower Bounds using
                                  Co-Nondeterminism: Finding Induced
                                  Hereditary Subgraphs . . . . . . . . . . 4:1--4:??

ACM Transactions on Computation Theory
Volume 7, Number 2, May, 2015

               Yuval Filmus and   
            Toniann Pitassi and   
                Rahul Santhanam   Exponential Lower Bounds for AC$0$-Frege
                                  Imply Superpolynomial Frege Lower Bounds 5:1--5:??
         Markus Bläser and   
                   Bodo Manthey   Smoothed Complexity Theory . . . . . . . 6:1--6:??
                 Hubie Chen and   
             Moritz Müller   The Fine Classification of Conjunctive
                                  Queries and Parameterized Logarithmic
                                  Space  . . . . . . . . . . . . . . . . . 7:1--7:??
         Balagopal Komarath and   
                  Jayalal Sarma   Pebbling, Entropy, and Branching Program
                                  Size Lower Bounds  . . . . . . . . . . . 8:1--8:??
             Ryan O'Donnell and   
                      Yi Wu and   
                      Yuan Zhou   Hardness of Max-2Lin and Max-3Lin over
                                  Integers, Reals, and Large Cyclic Groups 9:1--9:??

ACM Transactions on Computation Theory
Volume 7, Number 3, July, 2015

            Andris Ambainis and   
            William Gasarch and   
         Aravind Srinivasan and   
                    Andrey Utis   Lower Bounds on the Deterministic and
                                  Quantum Communication Complexity of
                                  Hamming-Distance Problems  . . . . . . . 10:1--10:??
                Mark Jerrum and   
                    Kitty Meeks   Some Hard Families of Parameterized
                                  Counting Problems  . . . . . . . . . . . 11:1--11:??
                  Adam Case and   
                   Jack H. Lutz   Mutual Dimension . . . . . . . . . . . . 12:1--12:??
             Henning Fernau and   
Alejandro López-Ortiz and   
           Jazmín Romero   Using Parametric Transformations Toward
                                  Polynomial Kernels for Packing Problems
                                  Allowing Overlaps  . . . . . . . . . . . 13:1--13:??

ACM Transactions on Computation Theory
Volume 7, Number 4, September, 2015

Pål Grònås Drange and   
             Fedor V. Fomin and   
           Michal Pilipczuk and   
                Yngve Villanger   Exploring the Subexponential Complexity
                                  of Completion Problems . . . . . . . . . 14:1--14:??
                 Oded Regev and   
                  Thomas Vidick   Quantum XOR Games  . . . . . . . . . . . 15:1--15:??
             Oded Goldreich and   
                        Or Meir   Input-Oblivious Proof Systems and a
                                  Uniform Complexity Perspective on P/poly 16:1--16:??
              Jason Teutsch and   
                  Marius Zimand   On Approximate Decidability of Minimal
                                  Programs . . . . . . . . . . . . . . . . 17:1--17:??


ACM Transactions on Computation Theory
Volume 8, Number 1, February, 2016

             Stefan Kratsch and   
         Dániel Marx and   
          Magnus Wahlström   Parameterized Complexity and
                                  Kernelizability of Max Ones and Exact
                                  Ones Problems  . . . . . . . . . . . . . 1:1--1:??
                 Ilya Volkovich   Characterizing Arithmetic Read-Once
                                  Formulae . . . . . . . . . . . . . . . . 2:1--2:??
                Sylvain Schmitz   Complexity Hierarchies beyond Elementary 3:1--3:??
                      Nir Ailon   An $ \Omega ((n \log n) / R) $ Lower
                                  Bound for Fourier Transform Computation
                                  in the $R$-Well Conditioned Model  . . . 4:1--4:??

ACM Transactions on Computation Theory
Volume 8, Number 2, May, 2016

              Eldar Fischer and   
          Yonatan Goldhirsh and   
                   Oded Lachish   Testing Read-Once Formula Satisfaction   5:1--5:??
         Michael R. Fellows and   
             Danny Hermelin and   
           Frances Rosamond and   
                 Hadas Shachnai   Tractable Parameterizations for the
                                  Minimum Linear Arrangement Problem . . . 6:1--6:??
             Oded Goldreich and   
                       Dana Ron   On Sample-Based Testers  . . . . . . . . 7:1--7:??

ACM Transactions on Computation Theory
Volume 8, Number 3, May, 2016

               Mrinal Kumar and   
          Gaurav Maheshwari and   
                  Jayalal Sarma   Arithmetic Circuit Lower Bounds via
                                  Maximum-Rank of Partial Derivative
                                  Matrices . . . . . . . . . . . . . . . . 8:1--8:??
                Peter Fulla and   
         Stanislav Zivný   A Galois Connection for Weighted
                                  (Relational) Clones of Infinite Size . . 9:1--9:??
                Ishay Haviv and   
                     Oded Regev   The List-Decoding Size of Fourier-Sparse
                                  Boolean Functions  . . . . . . . . . . . 10:1--10:??
                Dung Nguyen and   
                 Alan L. Selman   Structural Properties of
                                  Nonautoreducible Sets  . . . . . . . . . 11:1--11:??
         Andreas Göbel and   
        Leslie Ann Goldberg and   
                 David Richerby   Counting Homomorphisms to Square-Free
                                  Graphs, Modulo 2 . . . . . . . . . . . . 12:1--12:??

ACM Transactions on Computation Theory
Volume 8, Number 4, July, 2016

        Ioannis Caragiannis and   
        Christos Kaklamanis and   
               Maria Kyropoulou   Limitations of Deterministic Auction
                                  Design for Correlated Bidders  . . . . . 13:1--13:??
               Rohit Gurjar and   
              Arpita Korwar and   
             Jochen Messner and   
               Simon Straub and   
                Thomas Thierauf   Planarizing Gadgets for Perfect Matching
                                  Do Not Exist . . . . . . . . . . . . . . 14:1--14:??
                   Dana Ron and   
                     Gilad Tsur   The Power of an Example: Hidden Set Size
                                  Approximation Using Group Queries and
                                  Conditional Sampling . . . . . . . . . . 15:1--15:??
            Anna Gál and   
             Jing-Tang Jang and   
               Nutan Limaye and   
              Meena Mahajan and   
          Karteek Sreenivasaiah   Space-Efficient Approximations for
                                  Subset Sum . . . . . . . . . . . . . . . 16:1--16:??
                 Massimo Lauria   A Rank Lower Bound for Cutting Planes
                                  Proofs of Ramsey's Theorem . . . . . . . 17:1--17:??
                 Emanuele Viola   Quadratic Maps Are Hard to Sample  . . . 18:1--18:??


ACM Transactions on Computation Theory
Volume 9, Number 1, December, 2016

                      P. Hrubes   On Hardness of Multilinearization and
                                  VNP-Completeness in Characteristic $2$   1:1--1:??
              Andreas Krebs and   
               Nutan Limaye and   
              Meena Mahajan and   
          Karteek Sreenivasaiah   Small Depth Proof Systems  . . . . . . . 2:1--2:??
                  V. Arvind and   
             P. S. Joglekar and   
                        S. Raja   Noncommutative Valiant's Classes:
                                  Structure and Complete Problems  . . . . 3:1--3:??
                Lila Fontes and   
                 Rahul Jain and   
         Iordanis Kerenidis and   
            Sophie Laplante and   
         Mathieu Lauri\`ere and   
   Jérémie Roland   Relative Discrepancy Does Not Separate
                                  Information and Communication Complexity 4:1--4:??
                 Paul Beame and   
           Nathan Grosshans and   
            Pierre McKenzie and   
                   Luc Segoufin   Nondeterminism and An Abstract
                                  Formulation of Neciporuk's Lower Bound
                                  Method . . . . . . . . . . . . . . . . . 5:1--5:??

ACM Transactions on Computation Theory
Volume 9, Number 2, May, 2017

           Sergei Artemenko and   
                 Ronen Shaltiel   Pseudorandom Generators with Optimal
                                  Seed Length for Non-Boolean Poly-Size
                                  Circuits . . . . . . . . . . . . . . . . 6:1--6:??
        Arnab Bhattacharyya and   
                 Sivakanth Gopi   Lower Bounds for Constant Query
                                  Affine-Invariant LCCs and LTCs . . . . . 7:1--7:??
               Rohit Gurjar and   
              Arpita Korwar and   
             Jochen Messner and   
                Thomas Thierauf   Exact Perfect Matching in Complete
                                  Graphs . . . . . . . . . . . . . . . . . 8:1--8:??
            Andreas Galanis and   
        Leslie Ann Goldberg and   
                    Mark Jerrum   A Complexity Trichotomy for
                                  Approximately Counting List
                                  $H$-Colorings  . . . . . . . . . . . . . 9:1--9:??
               Anant Dhayal and   
              Jayalal Sarma and   
                Saurabh Sawlani   Min/Max-Poly Weighting Schemes and the
                                  NL versus UL Problem . . . . . . . . . . 10:1--10:??

ACM Transactions on Computation Theory
Volume 9, Number 3, October, 2017

                 Hubie Chen and   
                  Benoit Larose   Asking the Metaquestions in Constraint
                                  Tractability . . . . . . . . . . . . . . 11:1--11:??
          Michael Elberfeld and   
              Pascal Schweitzer   Canonizing Graphs of Bounded Tree Width
                                  in Logspace  . . . . . . . . . . . . . . 12:1--12:??
               Markus L. Schmid   Finding Consensus Strings with Small
                                  Length Difference between Input and
                                  Solution Strings . . . . . . . . . . . . 13:1--13:??
             Anna Adamaszek and   
           Tomasz Kociumaka and   
           Marcin Pilipczuk and   
               Michal Pilipczuk   Hardness of Approximation for Strip
                                  Packing  . . . . . . . . . . . . . . . . 14:1--14:??
                     Hubie Chen   Proof Complexity Modulo the Polynomial
                                  Hierarchy: Understanding Alternation as
                                  a Source of Hardness . . . . . . . . . . 15:1--15:??

ACM Transactions on Computation Theory
Volume 9, Number 4, January, 2018

                Kazuo Iwama and   
                 Yuichi Yoshida   Parameterized Testability  . . . . . . . 16:1--16:??
Ramesh Krishnan S. Pallavoor and   
        Sofya Raskhodnikova and   
                   Nithin Varma   Parameterized Property Testing of
                                  Functions  . . . . . . . . . . . . . . . 17:1--17:??
           Michal Pilipczuk and   
                 Marcin Wrochna   On Space Efficiency of Algorithms
                                  Working on Structural Decompositions of
                                  Graphs . . . . . . . . . . . . . . . . . 18:1--18:??
       Diptarka Chakraborty and   
               Raghunath Tewari   An $ O(n \epsilon) $ Space and
                                  Polynomial Time Algorithm for
                                  Reachability in Directed Layered Planar
                                  Graphs . . . . . . . . . . . . . . . . . 19:1--19:??
               Ching-Lueh Chang   Metric $1$-Median Selection: Query
                                  Complexity vs. Approximation Ratio . . . 20:1--20:??


ACM Transactions on Computation Theory
Volume 10, Number 1, January, 2018

          Baris Aydinlioglu and   
                      Eric Bach   Affine Relativization: Unifying the
                                  Algebrization and Relativization
                                  Barriers . . . . . . . . . . . . . . . . 1:1--1:??
                  Thomas Watson   Communication Complexity of Statistical
                                  Distance . . . . . . . . . . . . . . . . 2:1--2:??
           Matthew Anderson and   
          Michael A. Forbes and   
      Ramprasad Saptharishi and   
               Amir Shpilka and   
                   Ben Lee Volk   Identity Testing and Lower Bounds for
                                  Read-$k$ Oblivious Algebraic Branching
                                  Programs . . . . . . . . . . . . . . . . 3:1--3:??
        Mika Göös and   
               T. S. Jayram and   
            Toniann Pitassi and   
                  Thomas Watson   Randomized Communication versus
                                  Partition Number . . . . . . . . . . . . 4:1--4:??

ACM Transactions on Computation Theory
Volume 10, Number 2, May, 2018

             Ryan O'Donnell and   
                  A. C. Cem Say   The Weakness of CTC Qubits and the Power
                                  of Approximate Counting  . . . . . . . . 5:1--5:??
          Christian Komusiewicz   Tight Running Time Lower Bounds for
                                  Vertex Deletion Problems . . . . . . . . 6:1--6:??
               Jack H. Lutz and   
                      Neil Lutz   Algorithmic Information, Plane Kakeya
                                  Sets, and Conditional Dimension  . . . . 7:1--7:??
            Sevag Gharibian and   
                   Jamie Sikora   Ground State Connectivity of Local
                                  Hamiltonians . . . . . . . . . . . . . . 8:1--8:??
              Ivan Bliznets and   
                Marek Cygan and   
               Pawel Komosa and   
               Michal Pilipczuk   Hardness of Approximation for $H$-free
                                  Edge Modification Problems . . . . . . . 9:1--9:??

ACM Transactions on Computation Theory
Volume 10, Number 3, June, 2018

             Daniel Minahan and   
                 Ilya Volkovich   Complete Derandomization of Identity
                                  Testing and Reconstruction of Read-Once
                                  Formulas . . . . . . . . . . . . . . . . 10:1--10:??
               Yuval Filmus and   
                Guy Kindler and   
            Elchanan Mossel and   
                    Karl Wimmer   Invariance Principle on the Slice  . . . 11:1--11:??
              Johan Thapper and   
         Stanislav Zivný   The Limits of SDP Relaxations for
                                  General-Valued CSPs  . . . . . . . . . . 12:1--12:??
           Marcin Pilipczuk and   
          Magnus Wahlström   Directed Multicut is $ W[1] $-hard, Even
                                  for Four Terminal Pairs  . . . . . . . . 13:1--13:??
                Chin Ho Lee and   
                 Emanuele Viola   The Coin Problem for Product Tests . . . 14:1--14:??

ACM Transactions on Computation Theory
Volume 10, Number 4, October, 2018

              Moses Ganardi and   
                Danny Hucke and   
          Daniel König and   
                  Markus Lohrey   Circuits and Expressions over Finite
                                  Semirings  . . . . . . . . . . . . . . . 15:1--15:??
     Rishiraj Bhattacharyya and   
             Sourav Chakraborty   Property Testing of Joint Distributions
                                  using Conditional Samples  . . . . . . . 16:1--16:??
                   Heng Guo and   
                      Pinyan Lu   Uniqueness, Spatial Mixing, and
                                  Approximation for Ferromagnetic $2$-Spin
                                  Systems  . . . . . . . . . . . . . . . . 17:1--17:??
           Akanksha Agrawal and   
          Daniel Lokshtanov and   
            Amer E. Mouawad and   
                  Saket Saurabh   Simultaneous Feedback Vertex Set: a
                                  Parameterized Perspective  . . . . . . . 18:1--18:??
           Lucas Boczkowski and   
         Iordanis Kerenidis and   
 Frédéric Magniez   Streaming Communication Protocols  . . . 19:1--19:??