Last update:
Sat Oct 4 07:06:09 MDT 2025
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:??
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:??
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:??
Yitong Yin Cell-Probe Proofs . . . . . . . . . . . 1:1--1:??
Martin Hoefer and
Alexander Souza Tradeoffs and Average-Case Equilibria in
Selfish Routing . . . . . . . . . . . . 2:1--2:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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:??
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
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
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
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
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
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
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
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
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
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:??
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:??
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:??
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:??
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:??
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:??
Emirhan Gürpìnar and
Andrei Romashchenko Communication Complexity of the Secret
Key Agreement in Algorithmic Information
Theory . . . . . . . . . . . . . . . . . 13:1--13:37
Chandan Saha and
Bhargav Thankey Hitting Sets for Orbits of Circuit
Classes and Polynomial Families . . . . 14:1--14:50
Svyatoslav Gryaznov and
Sergei Ovcharov and
Artur Riazanov Resolution Over Linear Equations:
Combinatorial Games for Tree-like Size
and Space . . . . . . . . . . . . . . . 15:1--15:15
Michael Kuhn and
Daniel Lokshtanov and
Zachary Miller Lower Bound for Independence Covering in
C$_4$-free Graphs . . . . . . . . . . . 16:1--16:7
Michael Lampis and
Manolis Vasilakis Structural Parameterizations for Two
Bounded Degree Problems Revisited . . . 17:1--17:51
Jin-Yi Cai and
Ben Young Planar #CSP Equality Corresponds to
Quantum Isomorphism --- a Holant
Viewpoint . . . . . . . . . . . . . . . 18:1--18:41
Ivan Geffner and
Joseph Y. Halpern Bounding the communication complexity of
fault-tolerant common coin tossing . . . 19:1--19:10
Lane A. Hemaspaandra and
Mandar Juvekar and
Arian Nadjimzadah and
Patrick A. Phillips Gaps, Ambiguity, and Establishing
Complexity-Class Containments via
Iterative Constant-Setting . . . . . . . 20:1--20:26
Srinivasan Arunachalam and
Joao F. Doriguello Matrix hypercontractivity, streaming
algorithms and LDCs: the large alphabet
case . . . . . . . . . . . . . . . . . . 21:1--21:38
Olaf Beyersdorff and
Joshua Lewis Blinkhorn and
Tomás Peitl Strong (D)QBF Dependency Schemes via
Implication-free Resolution Paths . . . 22:1--22:25
C. S. Bhargav and
Sagnik Dutta and
Nitin Saxena Improved Lower Bound, and Proof Barrier,
for Constant Depth Algebraic Circuits 23:1--23:22
Christian Komusiewicz and
Nils Morawietz Finding 3-Swap-Optimal Independent Sets
and Dominating Sets is Hard . . . . . . 1:1--1:31
Daniel Lokshtanov and
Maadapuzhi-Sridharan Ramanujan and
Saket Saurabh and
Roohani Sharma and
Meirav Zehavi Wannabe Bounded Treewidth Graphs Admit a
Polynomial Kernel for Directed Feedback
Vertex Set . . . . . . . . . . . . . . . 2:1--2:28
Eric Allender and
Jacob Gray and
Saachi Mutreja and
Harsha Tirumala and
Pengxiang Wang Robustness for Space-Bounded Statistical
Zero Knowledge . . . . . . . . . . . . . 3:1--3:25
Ishay Haviv The Chromatic Number of Kneser
Hypergraphs via Consensus Division . . . 4:1--4:23
Jesse Beisegel and
Fabienne Ratajczak and
Robert Scheffler Computing Hamiltonian Paths with Partial
Order Restrictions . . . . . . . . . . . 5:1--5:24
Ildikó Schlotter and
Ágnes Cseh Maximum-utility Popular Matchings with
Bounded Instability . . . . . . . . . . 6:1--6:35
Angus Lowe and
Ashwin Nayak Lower Bounds for Learning Quantum States
with Single-Copy Measurements . . . . . 7:1--7:42
Konrad Majewski and
Micha\l Pilipczuk and
Marek Soko\lowski Maintaining CMSO$_2$ properties on
dynamic structures with bounded feedback
vertex number . . . . . . . . . . . . . 8:1--8:72
Sylvain Guillemot Parameterized covering in
semi-ladder-free hypergraphs . . . . . . 9:1--9:15
Jacob Focke and
Dániel Marx and
Fionn Mc Inerney and
Daniel Neuen and
Govind S. Sankar and
Philipp Schepper and
Philip Wellnitz Tight Complexity Bounds for Counting
Generalized Dominating Sets in
Bounded-Treewidth Graphs. Part II:
Hardness Results . . . . . . . . . . . . 10:1--10:101
Aleksa Stankovic Some Results on Approximability of
Minimum Sum Vertex Cover . . . . . . . . 11:1--11:28
Pranav Bisht and
Nitin Saxena Derandomization via Symmetric Polytopes:
Poly-time Factorization of Certain
Sparse Polynomials . . . . . . . . . . . 12:1--12:20
Bruno Cavalar and
Igor Oliveira Boolean Circuit Complexity and
Two-Dimensional Cover Problems . . . . . 13:1--13:23
Venkatesan Guruswami and
Xin Lyu and
Xiuhan Wang Range Avoidance for Low-Depth Circuits
and Connections to Pseudorandomness . . 14:1--14:23
Satyadev Nandakumar and
Akhil S. and
Prateek Vishnoi Effective Continued Fraction Dimension
versus Effective Hausdorff Dimension of
Reals . . . . . . . . . . . . . . . . . 15:1--15:18