Last update: Tue Aug 20 08:50:32 MDT 2024
Volume 1, Number 1, February, 2009Lance 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:??