Theory of Computing Systems

In Memoriam - Alan Selman (1941 - 2021)

Foreword: a Commemorative Issue for Alan L. Selman

Elvira Mayordomo, Mitsunori Ogihara, Atri Rudra

Holographic Algorithms on Domains of General Size

Zhiguo Fu, Jin-Yi Cai

Subclasses of Ptime Interpreted by Programming Languages

Siddharth Bhaskar, Cynthia Kop, Jakob Grue Simonsen

Dimension and the Structure of Complexity Classes

Jack H. Lutz, Neil Lutz, Elvira Mayordomo

Ergodic Theorems and Converses for PSPACE Functions

Satyadev Nandakumar, Subin Pulari

The Complexity of Grid Coloring

Daniel Apon, William Gasarch, Kevin Lawler

Effective Guessing Has Unlikely Consequences

András Z. Salamon, Michael Wehar

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

M. Ogihara, K. Uchizawa

Arithmetic Circuits, Structured Matrices and (not so) Deep Learning

Atri Rudra

Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality

Joshua A. Grochow