Accepted Papers
(in the order of submission)
- One-tape Turing machine and branching program lower bounds for MCSP
- Good r-divisions Imply Optimal Amortized Decremental Biconnectivity
- Online Simple Knapsack with Reservation Costs
- Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
- Finding an Optimal Alphabet Ordering for Lyndon Factorization is Hard
- Spectrum preserving short cycle removal on regular graphs
- Inference and mutual information on random factor graphs
- Rice-like theorems for automata networks
- b-Coloring Parameterized by Clique-Width
- Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points
- An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
- 6-Uniform Maker-Breaker Game Is PSPACE-Complete
- Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
- Geometric Cover with Outliers Removal
- Complexity of the list homomorphism problem in hereditary graph classes
- An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
- A characterization of wreath products where knapsack is decidable
- On Euclidean Steiner (1+epsilon)-Spanners
- Digraph Coloring and Distance to Acyclicity
- Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
- Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and their Applications
- Solving one variable word equations in free groups in cubic time
- Exploiting Dense Structures in Parameterized Complexity
- Resolution with Symmetry Rule applied to Linear Equations
- Achieving anonymity via weak lower bound constraints for k-median and k-means
- Subgroup membership in GL(2,Z)
- Synchronizing Strongly Connected Partial DFAs
- On testing isomorphism of polynomials, algebras, and multilinear forms
- A faster algorithm for finding Tarski fixed points
- The Edit Distance to $k$-Subsequence Universality
- Barrington Plays Cards: The Complexity of Card-based Protocols
- Distance Computations in the Hybrid Network Model via Oracle Simulations
- Tight Approximation Guarantees for Concave Coverage Problems
- A Ramsey Theorem for Finite Monoids
- Binary Matrix Completion Under Diameter Constraints
- A Unified Framework of Quantum Walk Search
- Diverse Collections in Matroids and Graphs
- Bidimensional linear recursive sequences and universality of unambiguous register automata (Extended abstract)
- Efficiently Testing Simon’s Congruence
- Locality-sensitive hashing for efficient similar polygon retrieval
- The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem
- Absorbing patterns in BST-like expression-trees
- Quantum approximate counting with nonadaptive Grover iterations
- The Complexity of the Distributed Constraint Satisfaction Problem
- Parameterised Counting in Logspace
- Lower bounds for graph-walking automata
- Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
- A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
- Cluster Editing parameterized above modification-disjoint P_3-packings
- An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
- Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
- A Framework of Quantum Strong Exponential-Time Hypotheses
- Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
- Church Synthesis on Register Automata over Infinite Ordered Data Domains
- An Improved Sketching Bound for Edit Distance
- Reachability in two-parametric timed automata with one parameter is EXPSPACE-complete