Table of contents for issues of ACM Transactions on Computation Theory

Last update: Tue Aug 20 08:50:32 MDT 2024                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
Volume 11, Number 1, January, 2019
Volume 11, Number 2, April, 2019
Volume 11, Number 3, June, 2019
Volume 11, Number 4, September, 2019
Volume 12, Number 1, February, 2020
Volume 12, Number 2, May, 2020
Volume 12, Number 3, July, 2020
Volume 12, Number 4, December, 2020
Volume 13, Number 1, March, 2021
Volume 13, Number 2, June, 2021
Volume 13, Number 3, September, 2021
Volume 13, Number 4, December, 2021
Volume 14, Number 1, March, 2022
Volume 14, Number 2, June, 2022
Volume 14, Number 3--4, December, 2022
Volume 15, Number 1--2, June, 2023
Volume 15, Number 3--4, December, 2023
Volume 16, Number 1, March, 2024
Volume 16, Number 2, June, 2024


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:??


ACM Transactions on Computation Theory
Volume 11, Number 1, January, 2019

              Moses Ganardi and   
                  Markus Lohrey   A Universal Tree Balancing Theorem . . . 1:1--1:??
               Neeraj Kayal and   
                Vineet Nair and   
               Chandan Saha and   
       Sébastien Tavenas   Reconstruction of Full Rank Algebraic
                                  Branching Programs . . . . . . . . . . . 2:1--2:??
           Beno\^\it Larose and   
             Barnaby Martin and   
           Daniël Paulusma   Surjective H-Colouring over Reflexive
                                  Digraphs . . . . . . . . . . . . . . . . 3:1--3:??
                Peter Fulla and   
              Hannes Uppman and   
         Stanislav Zivný   The Complexity of Boolean Surjective
                                  General-Valued CSPs  . . . . . . . . . . 4:1--4:??
                Kazuo Iwama and   
                   Atsuki Nagao   Read-Once Branching Programs for Tree
                                  Evaluation Problems  . . . . . . . . . . 5:1--5:??

ACM Transactions on Computation Theory
Volume 11, Number 2, April, 2019

                 Eric Blais and   
  Clément L. Canonne and   
                        Tom Gur   Distribution Testing Lower Bounds via
                                  Reductions from Communication Complexity 6:1--6:??
                 Jin-Yi Cai and   
          Michael Kowalczyk and   
                 Tyson Williams   Gadgets and Anti-Gadgets Leading to a
                                  Complexity Dichotomy . . . . . . . . . . 7:1--7:??
      Krishnamoorthy Dinesh and   
               Sajin Koroth and   
                  Jayalal Sarma   Characterization and Lower Bounds for
                                  Branching Program Size using Projective
                                  Dimension  . . . . . . . . . . . . . . . 8:1--8:??
         Iordanis Kerenidis and   
           Adi Rosén and   
                Florent Urrutia   Multi-Party Protocols, Information
                                  Complexity and Privacy . . . . . . . . . 9:1--9:??
                   C. Ramya and   
          B. V. Raghavendra Rao   Lower bounds for Sum and Sum of Products
                                  of Read-once Formulas  . . . . . . . . . 10:1--10:??
             Sudeshna Kolay and   
              Fahad Panolan and   
                  Saket Saurabh   Communication Complexity and Graph
                                  Families . . . . . . . . . . . . . . . . 11:1--11:??

ACM Transactions on Computation Theory
Volume 11, Number 3, June, 2019

          Grant Schoenebeck and   
                  Biaoshuai Tao   Beyond Worst-case (In)approximability of
                                  Nonsubmodular Influence Maximization . . 12:1--12:??
              Marthe Bonamy and   
            \lUkasz Kowalik and   
          Micha\l Pilipczuk and   
          Arkadiusz Soca\la and   
                 Marcin Wrochna   Tight Lower Bounds for the Complexity of
                                  Multicoloring  . . . . . . . . . . . . . 13:1--13:??
                  Timothy Black   Monotone Properties of $k$-Uniform
                                  Hypergraphs Are Weakly Evasive . . . . . 14:1--14:??
                   Nir Aviv and   
                  Amnon Ta-Shma   On the Entropy Loss and Gap of
                                  Condensers . . . . . . . . . . . . . . . 15:1--15:??
          Baris Aydinlioglu and   
                      Eric Bach   Corrigendum to Affine Relativization:
                                  Unifying the Algebrization and
                                  Relativization Barriers  . . . . . . . . 16:1--16:??
             Oded Goldreich and   
                    Tom Gur and   
               Ilan Komargodski   Strong Locally Testable Codes with
                                  Relaxed Local Decoders . . . . . . . . . 17:1--17:??
           Akanksha Agrawal and   
          Daniel Lokshtanov and   
              Saket Saurabh and   
                  Meirav Zehavi   Split Contraction: The Untold Story  . . 18:1--18:??

ACM Transactions on Computation Theory
Volume 11, Number 4, September, 2019

                 Emanuele Viola   Constant-Error Pseudorandomness Proofs
                                  from Hardness Require Majority . . . . . 19:1--19:??
                    Ishay Haviv   On Minrank and Forbidden Subgraphs . . . 20:1--20:??
               Ravi Boppana and   
         Johan Håstad and   
                Chin Ho Lee and   
                 Emanuele Viola   Bounded Independence versus Symmetric
                                  Tests  . . . . . . . . . . . . . . . . . 21:1--21:??
Mateus De Oliveira Oliveira and   
            Pavel Pudlák   Representations of Monotone Boolean
                                  Functions by Linear Programs . . . . . . 22:1--22:??
        Leslie Ann Goldberg and   
                    Mark Jerrum   Approximating Pairwise Correlations in
                                  the Ising Model  . . . . . . . . . . . . 23:1--23:??
                 Eric Blais and   
  Clément L. Canonne and   
                 Talya Eden and   
                  Amit Levi and   
                       Dana Ron   Tolerant Junta Testing and the
                                  Connection to Submodular Optimization
                                  and Function Isomorphism . . . . . . . . 24:1--24:??
                Dominik Scheder   PPSZ for $ k \geq 5 $: More Is Better    25:1--25:??
           Olaf Beyersdorff and   
                 Leroy Chew and   
          Mikolás Janota   New Resolution-Based QBF Calculi and
                                  Their Proof Complexity . . . . . . . . . 26:1--26:??
              Eric Allender and   
               Shuichi Hirahara   New Insights on the (Non-)Hardness of
                                  Circuit Minimization and Related
                                  Problems . . . . . . . . . . . . . . . . 27:1--27:??
          Bart M. P. Jansen and   
                Astrid Pieterse   Optimal Sparsification for Some Binary
                                  CSPs Using Low-Degree Polynomials  . . . 28:1--28:??


ACM Transactions on Computation Theory
Volume 12, Number 1, February, 2020

                 Ryan O'Donnell   Editorial from the New Editor-in-Chief   1e:1--1e:1
               Arijit Ghosh and   
             Sudeshna Kolay and   
                Gopinath Mishra   FPT Algorithms for Embedding into
                                  Low-Complexity Graphic Metrics . . . . . 1:1--1:41
               Neeraj Kayal and   
                Vineet Nair and   
                   Chandan Saha   Separation Between Read-once Oblivious
                                  Algebraic Branching Programs (ROABPs)
                                  and Multilinear Depth-three Circuits . . 2:1--2:27
         Edith Hemaspaandra and   
       Lane A. Hemaspaandra and   
                  Curtis Menton   Search versus Decision for Election
                                  Manipulation Problems  . . . . . . . . . 3:1--3:42
           Montserrat Hermo and   
                      Ana Ozaki   Exact Learning: On the Boundary between
                                  Horn and CNF . . . . . . . . . . . . . . 4:1--4:25
                   Mrinal Kumar   On the Power of Border of Depth-3
                                  Arithmetic Circuits  . . . . . . . . . . 5:1--5:8
             Henning Fernau and   
               Florin Manea and   
              Robert Mercas and   
               Markus L. Schmid   Pattern Matching with Variables:
                                  Efficient Algorithms and Complexity
                                  Results  . . . . . . . . . . . . . . . . 6:1--6:37
          Elazar Goldenberg and   
                  Karthik C. S.   Toward a General Direct Product Testing
                                  Theorem  . . . . . . . . . . . . . . . . 7:1--7:18

ACM Transactions on Computation Theory
Volume 12, Number 2, May, 2020

               Rohit Gurjar and   
                   Ben Lee Volk   Pseudorandom Bits for Oblivious
                                  Branching Programs . . . . . . . . . . . 8:1--8:12
              Nicola Galesi and   
          Navid Talebanfard and   
            Jacobo Torán   Cops--Robber Games and the Resolution of
                                  Tseitin Formulas . . . . . . . . . . . . 9:1--9:22
           Olaf Beyersdorff and   
                 Luke Hinde and   
                Ján Pich   Reasons for Hardness in QBF Proof
                                  Systems  . . . . . . . . . . . . . . . . 10:1--10:27
          Andrei A. Bulatov and   
         Stanislav Zivný   Approximate Counting CSP Seen from the
                                  Other Side . . . . . . . . . . . . . . . 11:1--11:19
             David J. Rosenbaum   Beating the Generator-Enumeration Bound
                                  for Solvable-Group Isomorphism . . . . . 12:1--12:18
          Victor Lagerkvist and   
          Magnus Wahlström   Sparsification of SAT and CSP Problems
                                  via Tractable Extensions . . . . . . . . 13:1--13:29
                  Thomas Watson   Quadratic Simulations of Merlin--Arthur
                                  Games  . . . . . . . . . . . . . . . . . 14:1--14:11

ACM Transactions on Computation Theory
Volume 12, Number 3, July, 2020

                Jacob Focke and   
        Leslie Ann Goldberg and   
         Stanislav Zivný   The Complexity of Approximately Counting
                                  Retractions  . . . . . . . . . . . . . . 15:1--15:43
          Alessandro Chiesa and   
              Peter Manohar and   
                   Igor Shinkar   Testing Linearity against Non-signaling
                                  Strategies . . . . . . . . . . . . . . . 16:1--16:51
                   Stasys Jukna   Coin Flipping in Dynamic Programming Is
                                  Almost Useless . . . . . . . . . . . . . 17:1--17:26
           Md Lutfar Rahman and   
                  Thomas Watson   Complexity of Unordered CNF Games  . . . 18:1--18:18
                 Dusan Knop and   
          Micha\l Pilipczuk and   
                 Marcin Wrochna   Tight Complexity Lower Bounds for
                                  Integer Linear Programming with Few
                                  Constraints  . . . . . . . . . . . . . . 19:1--19:19
        Mika Göös and   
                  Thomas Watson   A Lower Bound for Sampling Disjoint Sets 20:1--20:13
           Mahdi Cheraghchi and   
         Valentine Kabanets and   
                Zhenjian Lu and   
           Dimitrios Myrisiotis   Circuit Lower Bounds for MCSP from Local
                                  Pseudorandom Generators  . . . . . . . . 21:1--21:27

ACM Transactions on Computation Theory
Volume 12, Number 4, December, 2020

              Robert Ganian and   
             Ronald de Haan and   
                  Iyad Kanj and   
                 Stefan Szeider   On Existential MSO and Its Relation to
                                  ETH  . . . . . . . . . . . . . . . . . . 22:1--22:32
            Srikanth Srinivasan   Strongly Exponential Separation between
                                  Monotone VP and Monotone VNP . . . . . . 23:1--23:12
            Benny Applebaum and   
                    Barak Arkis   On the Power of Amortization in Secret
                                  Sharing: $d$-Uniform Secret Sharing and
                                  CDS with Constant Information Rate . . . 24:1--24:21
        Srikanth Srinivasan and   
           Utkarsh Tripathi and   
                   S. Venkitesh   Decoding Variants of Reed--Muller Codes
                                  over Finite Grids  . . . . . . . . . . . 25:1--25:11
      Vladimir V. Podolskii and   
          Alexander A. Sherstov   Inner Product and Set Disjointness:
                                  Beyond Logarithmically Many Parties  . . 26:1--26:28
                  Thomas Watson   A ZPP NP[1] Lifting Theorem  . . . . . . 27:1--27:20
             Oded Goldreich and   
                       Dana Ron   The Subgraph Testing Model . . . . . . . 28:1--28:32


ACM Transactions on Computation Theory
Volume 13, Number 1, March, 2021

          John M. Hitchcock and   
             Adewale Sekoni and   
                    Hadi Shafei   Polynomial-Time Random Oracles and
                                  Separating Complexity Classes  . . . . . 1:11--1:16
              Peter Jonsson and   
          Victor Lagerkvist and   
                      Biman Roy   Fine-Grained Time Complexity of
                                  Constraint Satisfaction Problems . . . . 2:1--2:32
             William Kretschmer   Lower Bounding the AND--OR Tree via
                                  Symmetrization . . . . . . . . . . . . . 3:1--3:11
             Florent Becker and   
                 Tom Besson and   
Jérôme Durand-Lose and   
   Aurélien Emmanuel and   
Mohammad-Hadi Foroughmand-Araabi and   
               Sama Goliaei and   
           Shahrzad Heydarshahi   Abstract Geometrical Computation 10: an
                                  Intrinsically Universal Family of Signal
                                  Machines . . . . . . . . . . . . . . . . 4:1--4:31
                 Emanuele Viola   AC0 Unpredictability . . . . . . . . . . 5:1--5:8
            Dmitry Itsykson and   
          Alexander Okhotin and   
                Vsevolod Oparin   Computational and Proof Complexity of
                                  Partial String Avoidability  . . . . . . 6:1--6:25
            Andris Ambainis and   
           Martins Kokainis and   
           Krisjanis Prusis and   
          Jevgenijs Vihrovs and   
              Aleksejs Zajakins   All Classical Adversary Methods Are
                                  Equivalent for Total Functions . . . . . 7:1--7:20

ACM Transactions on Computation Theory
Volume 13, Number 2, June, 2021

                Holger Dell and   
                 John Lapinskas   Fine-Grained Reductions from Approximate
                                  Counting to Decision . . . . . . . . . . 8:1--8:24
             Sushmita Gupta and   
           Pranabendu Misra and   
              Saket Saurabh and   
                  Meirav Zehavi   Popular Matching in Roommates Setting Is
                                  NP-hard  . . . . . . . . . . . . . . . . 9:1--9:20
             Fedor V. Fomin and   
          Daniel Lokshtanov and   
              Ivan Mihajlin and   
              Saket Saurabh and   
                  Meirav Zehavi   Computation of Hadwiger Number and
                                  Related Contraction Problems: Tight
                                  Lower Bounds . . . . . . . . . . . . . . 10:1--10:25
                 Jin-yi Cai and   
                  Artem Govorov   On a Theorem of Lovász that $ (\cdot, H)
                                  $ Determines the Isomorphism Type of $H$ 11:1--11:25
                    Qian Li and   
                   Xiaoming Sun   On the Sensitivity Complexity of
                                  $k$-Uniform Hypergraph Properties  . . . 12:1--12:13
Ivona Bezáková and   
            Andreas Galanis and   
        Leslie Ann Goldberg and   
             Daniel Stefankovic   The Complexity of Approximating the
                                  Matching Polynomial in the Complex Plane 13:1--13:37

ACM Transactions on Computation Theory
Volume 13, Number 3, September, 2021

                      Neil Lutz   Fractal Intersections and Products via
                                  Algorithmic Dimension  . . . . . . . . . 14:1--14:15
             Suryajith Chillara   On Computing Multilinear Polynomials
                                  Using Multi-$r$-ic Depth Four Circuits   16:1--16:21
              Akihiro Monde and   
            Yukiko Yamauchi and   
               Shuji Kijima and   
             Yamashita Masafumi   Can a Skywalker Localize the Midpoint of
                                  a Rope?  . . . . . . . . . . . . . . . . 17:1--17:23

ACM Transactions on Computation Theory
Volume 13, Number 4, December, 2021

            Prasad Chaugule and   
               Nutan Limaye and   
                   Aditya Varre   Variants of Homomorphism Polynomials
                                  Complete for Algebraic Complexity
                                  Classes  . . . . . . . . . . . . . . . . 21:1--21:26
     Srinivasan Arunachalam and   
         Sourav Chakraborty and   
       Michal Koucký and   
              Nitin Saurabh and   
                 Ronald De Wolf   Improved Bounds on Fourier Entropy and
                                  Min-entropy  . . . . . . . . . . . . . . 22:1--22:40
         Valentine Kabanets and   
               Sajin Koroth and   
                Zhenjian Lu and   
       Dimitrios Myrisiotis and   
               Igor C. Oliveira   Algorithms and Lower Bounds for De
                                  Morgan Formulas of Low-Communication
                                  Leaf Gates . . . . . . . . . . . . . . . 23:1--23:37
                   Mark Bun and   
            Nikhil S. Mande and   
                  Justin Thaler   Sign-rank Can Increase under
                                  Intersection . . . . . . . . . . . . . . 24:1--24:17
            Andreas Galanis and   
        Leslie Ann Goldberg and   
                  James Stewart   Fast Algorithms for General Spin Systems
                                  on Bipartite Expanders . . . . . . . . . 25:1--25:18
               Alex Brandts and   
             Marcin Wrochna and   
         Stanislav Zivný   The Complexity of Promise SAT on
                                  Non-Boolean Domains  . . . . . . . . . . 26:1--26:20
             Spoorthy Gunda and   
               Pallavi Jain and   
          Daniel Lokshtanov and   
              Saket Saurabh and   
              Prafullkumar Tale   On the Parameterized Approximability of
                                  Contraction to Classes of Chordal Graphs 27:1--27:40


ACM Transactions on Computation Theory
Volume 14, Number 1, March, 2022

                  Amit Levi and   
Ramesh Krishnan S. Pallavoor and   
        Sofya Raskhodnikova and   
                   Nithin Varma   Erasure-Resilient Sublinear-Time Graph
                                  Algorithms . . . . . . . . . . . . . . . 1:1--1:??
          Victor Lagerkvist and   
          Magnus Wahlström   The (Coarse) Fine-Grained Structure of
                                  NP-Hard SAT and CSP Problems . . . . . . 2:1--2:??
              Xuangui Huang and   
                 Emanuele Viola   Approximate Degree, Weight, and
                                  Indistinguishability . . . . . . . . . . 3:1--3:26
                   Dana Ron and   
                     Asaf Rosin   Optimal Distribution-Free Sample-Based
                                  Testing of Subsequence-Freeness with
                                  One-Sided Error  . . . . . . . . . . . . 4:1--4:??
Frédéric Magniez and   
                   Ashwin Nayak   Quantum Distributed Complexity of Set
                                  Disjointness on a Line . . . . . . . . . 5:1--5:22

ACM Transactions on Computation Theory
Volume 14, Number 2, June, 2022

               Ben Lee Volk and   
                   Mrinal Kumar   A Polynomial Degree Bound on Equations
                                  for Non-rigid Matrices and Small Linear
                                  Circuits . . . . . . . . . . . . . . . . 6:1--6:??
                Noah Singer and   
                    Madhu Sudan   Point-hyperplane Incidence Geometry and
                                  the Log-rank Conjecture  . . . . . . . . 7:1--7:??
                Samir Datta and   
               Nutan Limaye and   
        Prajakta Nimbhorkar and   
            Thomas Thierauf and   
                  Fabian Wagner   Planar Graph Isomorphism Is in Log-Space 8:1--8:??
            Vikraman Arvind and   
           Frank Fuhlbrueck and   
           Johannes Koebler and   
          Sebastian Kuhnert and   
                  Gaurav Rattan   The Parameterized Complexity of Fixing
                                  Number and Vertex Individualization in
                                  Graphs . . . . . . . . . . . . . . . . . 9:1--9:??

ACM Transactions on Computation Theory
Volume 14, Number 3--4, December, 2022

            Andreas Galanis and   
                   Heng Guo and   
                   Jiaheng Wang   Inapproximability of Counting Hypergraph
                                  Colourings . . . . . . . . . . . . . . . 10:1--10:??
          Laurent Bartholdi and   
           Michael Figelius and   
              Markus Lohrey and   
               Armin Weiß   Groups with ALOGTIME-hard Word Problems
                                  and PSPACE-complete Compressed Word
                                  Problems . . . . . . . . . . . . . . . . 11:1--11:??
        Tamio-Vesa Nakajima and   
       Stanislav \vZivný   Linearly Ordered Colourings of
                                  Hypergraphs  . . . . . . . . . . . . . . 12:1--12:??
             Fedor V. Fomin and   
           Petr A. Golovach and   
          Giannos Stamoulis and   
          Dimitrios M. Thilikos   An Algorithmic Meta-Theorem for Graph
                                  Modification to Planarity and FOL  . . . 13:1--13:??


ACM Transactions on Computation Theory
Volume 15, Number 1--2, June, 2023

         Prerona Chatterjee and   
          Ramprasad Saptharishi   Constructing Faithful Homomorphisms over
                                  Fields of Finite Characteristic  . . . . 1:1--1:??
 Lukás Folwarczný   On Protocols for Monotone Feasible
                                  Interpolation  . . . . . . . . . . . . . 2:1--2:??
            Yassine Hamoudi and   
 Frédéric Magniez   Quantum Time-Space Tradeoff for Finding
                                  Multiple Collision Pairs . . . . . . . . 3:1--3:??

ACM Transactions on Computation Theory
Volume 15, Number 3--4, December, 2023

      Andreas Emil Feldmann and   
             Dániel Marx   The Complexity Landscape of
                                  Fixed-Parameter Directed Steiner Network
                                  Problems . . . . . . . . . . . . . . . . 4:1--4:??
     Hugo Côté and   
                Pierre McKenzie   Catalytic Branching Programs from Groups
                                  and General Protocols  . . . . . . . . . 5:1--5:??
                  Meirav Zehavi   Forgetfulness Can Make You Faster: an $
                                  O*(8.097^k) $-time Algorithm for
                                  Weighted $3$-set $k$-packing . . . . . . 6:1--6:??
        Sayan Bandyapadhyay and   
             Fedor V. Fomin and   
           Petr A. Golovach and   
                 Kirill Simonov   Parameterized Complexity of Feature
                                  Selection for Categorical Data
                                  Clustering . . . . . . . . . . . . . . . 7:1--7:??
                 Hubie Chen and   
          Bart M. P. Jansen and   
            Karolina Okrasa and   
            Astrid Pieterse and   
           Pawe\l Rz\ka\.zewski   Sparsification Lower Bounds for List
                                  $H$-Coloring . . . . . . . . . . . . . . 8:1--8:??


ACM Transactions on Computation Theory
Volume 16, Number 1, March, 2024

           Ashley Montanaro and   
                 Changpeng Shao   Quantum Communication Complexity of
                                  Linear Regression  . . . . . . . . . . . 1:1--1:??
          Joshua A. Grochow and   
                   Youming Qiao   On $p$-Group Isomorphism:
                                  Search-to-Decision,
                                  Counting-to-Decision, and Nilpotency
                                  Class Reductions via Tensors . . . . . . 2:1--2:??
               Adam Kurpisz and   
       Samuli Leppänen and   
            Monaldo Mastrolilli   Tight Sum-of-squares Lower Bounds for
                                  Binary Polynomial Optimization Problems  3:1--3:??
          Bart M. P. Jansen and   
            Micha\l W\lodarczyk   Optimal Polynomial-Time Compression for
                                  Boolean Max CSP  . . . . . . . . . . . . 4:1--4:??

ACM Transactions on Computation Theory
Volume 16, Number 2, June, 2024

                 Jin-Yi Cai and   
                Daniel P. Szabo   Bounded Degree Nonnegative Counting CSP  5:1--5:??
           Olaf Beyersdorff and   
           Joshua Blinkhorn and   
              Meena Mahajan and   
         Tomás Peitl and   
                    Gaurav Sood   Hard QBFs for Merge Resolution . . . . . 6:1--6:??
                 Dean Doron and   
               Jack Murtagh and   
               Salil Vadhan and   
                David Zuckerman   Small-Space Spectral Sparsification via
                                  Bounded-Independence Sampling  . . . . . 7:1--7:??
            Konrad Majewski and   
Tomás Masarík and   
Jana Masaríková and   
            Karolina Okrasa and   
           Marcin Pilipczuk and   
           Pawe\l Rzazewski and   
              Marek Soko\lowski   Max Weight Independent Set in Graphs
                                  with No Long Claws: an Analog of the
                                  Gyárfás' Path Argument . . . . . . . . . . 8:1--8:??
       Nikhil Shekhar Mande and   
                 Swagato Sanyal   On parity decision trees for
                                  Fourier-sparse Boolean functions . . . . 9:1--9:??
            Manuel Bodirsky and   
                 Bertalan Bodor   A Complexity Dichotomy in Spatial
                                  Reasoning via Ramsey Theory  . . . . . . 10:1--10:??
      Daniel J. Rosenkrantz and   
          Madhav V. Marathe and   
                 S. S. Ravi and   
             Richard E. Stearns   Synchronous Dynamical Systems on
                                  Directed Acyclic Graphs: Complexity and
                                  Algorithms . . . . . . . . . . . . . . . 11:1--11:??
          Anup Bhattacharya and   
              Arijit Bishnu and   
               Arijit Ghosh and   
                Gopinath Mishra   Faster Counting and Sampling Algorithms
                                  using Colorful Decision Oracle . . . . . 12:1--12:??