ICALP 2023

Material Package

Added Since

Include only attachments uploaded after this date

Include*

Everything

Specific sessions

Specific contributions

Specific days

Sessions*

Track B

Graph Width Parameters: from Structure to Algorithms (GWP 2023)

50th ICALP Anniversary Session

Track A-4

Track A-1

Track A-2

Algorithmic Aspects of Temporal Graphs VI

Colloquium in honor of Friedhelm Meyer auf der Heide

Track A-3

ICALP 2023 Award-Winning Papers

Adjoint Homomorphism Counting Workshop (ad hoc)

Congestion Games

Workshop On Reachability, Recurrences, and Loops '23 (WORReLL'23)

Workshop on Recent Trends in Online Algorithms

Quantum Computing with Qiskit, and why Classical Algorithms still matter!

Presburger & Church Award Talks

Keynote talk

Award Ceremony & EATCS Award Talk & EATCS General Assembly

Combinatorial Reconfiguration

Algebraic Complexity Theory

CANCELED: [Computer Science for CONTINUOUS Data]

Include materials from selected sessions

Contributions*

50 Years of ICALP, Personal Reminiscences (in session "50th ICALP Anniversary Session")

#CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint (in session "Track A-2")

(Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (in session "Keynote talk")

A dichotomy for succinct representations of homomorphisms (in session "Track B")

A General Framework for Learning-Augmented Online Allocation (in session "Track A-2")

A Hyperbolic Extension of Kadison-Singer Type Results (in session "Track A-4")

A Sparse Johnson-Lindenstrauss Transform using Fast Hashing (in session "Track A-4")

A Tight $(1.5+\epsilon)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees (in session "Track A-1")

Action Codes (in session "Track B")

Algebraic Recognition of Regular Functions (in session "Track B")

Allocating Indivisible Items in a Fair Manner (in session "Colloquium in honor of Friedhelm Meyer auf der Heide")

Alonzo Church Award 2023 (in session "Presburger & Church Award Talks")

An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs (in session "Track A-1")

An Almost-Linear Time Algorithm for Maximum Flow and More (in session "Keynote talk")

An Efficient Algorithm for All-Pairs Bounded Edge Connectivity (in session "Track A-1")

An EPTAS for Budgeted Matching and Budgeted Matroid Intersection (in session "Track A-3")

An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs (in session "Track A-3")

Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle? (in session "Track B")

Approximate Nearest Neighbor for Polygonal Curves under Frechet Distance (in session "Track A-2")

Approximating Long Cycle Above Dirac’s Guarantee (in session "Track A-1")

Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm (in session "Track A-3")

Approximation Algorithms for Envy-Free Cake Division with Connected Pieces (in session "Track A-1")

Approximation Algorithms for Network Design in Non-Uniform Fault Models (in session "Track A-2")

Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem (in session "Track A-3")

Award Ceremony (in session "Award Ceremony & EATCS Award Talk & EATCS General Assembly")

Best Paper Track A: A 4/3 Approximation for 2-Vertex-Connectivity (in session "ICALP 2023 Award-Winning Papers")

Best Paper Track A: Online Learning and Disambiguations of Partial Concept Classes (in session "ICALP 2023 Award-Winning Papers")

Best Paper Track B: Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality (in session "ICALP 2023 Award-Winning Papers")

Best Student Paper Track A: Minimum Chain Cover in Almost Linear Time (in session "ICALP 2023 Award-Winning Papers")

Best Student Paper Track B: The Identity Problem in $\mathbb{Z} \wr \mathbb{Z}$ is decidable (in session "ICALP 2023 Award-Winning Papers")

Black-box Testing Liveness Properties of Partially Observable Stochastic Systems (in session "Track B")

Breaking the All Subsets Barrier for Min $k$-Cut (in session "Track A-1")

Broadcasting with Random Matrices (in session "Track A-3")

Canonical decompositions in monadically stable and bounded shrubdepth graph classes (in session "Track B")

Characterising memory in infinite games (in session "Track B")

Checking Refinement of Asynchronous Programs against Context-Free Specifications (in session "Track B")

Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs (in session "Track A-3")

Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds (in session "Track A-4")

Compositionality of planar perfect matchings, a universal and complete fragment of ZW-calculus (in session "Track B")

Compound Logics for Modification Problems (in session "Track A-1")

Connected k-Center and k-Diameter Clustering (in session "Track A-3")

Context-Bounded Analysis of Concurrent Programs (in session "Keynote talk")

Convergence of the number of period sets in strings (in session "Track A-4")

Cumulative Memory Lower Bounds for Randomized and Quantum Computation (in session "Track A-1")

Decidability of fully quantum nonlocal games with noisy maximally entangled states (in session "Track A-2")

Deterministic regular functions of infinite words (in session "Track B")

Dynamic Averaging Load Balancing on Arbitrary Graphs (in session "Track A-1")

EATCS Award 2023 (in session "Award Ceremony & EATCS Award Talk & EATCS General Assembly")

EATCS General Assembly 2023 (in session "Award Ceremony & EATCS Award Talk & EATCS General Assembly")

Efficient Caching with Reserves via Marking (in session "Track A-2")

Efficient Data Structures for Incremental Exact and Approximate Maximum Flow (in session "Track A-3")

Ellipsoid Fitting Up to a Constant (in session "Track A-2")

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player (in session "Track A-4")

Fast approximation of search trees on trees with centroid trees (in session "Track A-1")

Faster Matroid Partition Algorithms (in session "Track A-1")

Faster parameterized algorithms for modification problems to minor-closed classes (in session "Track A-2")

Faster submodular maximization for several classes of matroids (in session "Track A-1")

Fault-Tolerant ST-Diameter Oracles (in session "Track A-3")

Finding Almost Tight Witness Trees (in session "Track A-1")

First Order Logic on Pathwidth Revisited Again (in session "Track B")

Flipper games for monadically stable graph classes (in session "Track B")

Frameworks for Nonclairvoyant Network Design with Deadlines or Delay (in session "Track A-2")

From Formal Methods for Continuous Systems to the Safety of Neural Network Controllers (in session "50th ICALP Anniversary Session")

Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs (in session "Track A-1")

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra (in session "Track A-4")

How to Play Optimally for Regular Objectives? (in session "Track B")

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions (in session "Track A-1")

Improved Hardness Results for the Guided Local Hamiltonian Problem (in session "Track A-1")

Improved mixing for the convex polygon triangulation flip walk (in session "Track A-3")

Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians (in session "Track A-1")

Incremental Maximization via Continuization (in session "Track A-2")

Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes (in session "Track B")

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing (in session "Track A-3")

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability (in session "Track A-2")

Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes (in session "Track A-3")

List Decoding of Rank-Metric Codes with Row-to-Column Ratio Bigger Than 1/2 (in session "Track A-3")

Local Computation Algorithms for Hypergraph Coloring - following Beck's approach (in session "Track A-4")

Locality in online, dynamic, sequential, and distributed graph algorithms (in session "Track A-2")

Low Sample Complexity Participatory Budgeting (in session "Track A-1")

Low-depth arithmetic circuit lower bounds: Bypassing set-multilinearization (in session "Track A-4")

Lower Bounds for Pseudo-Deterministic Counting in a Stream (in session "Track A-4")

Matching Augmentation via Simultaneous Contractions (in session "Track A-1")

Monadic NIP in monotone classes of relational structures (in session "Track B")

Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering (in session "Track A-3")

Nearly Tight Spectral Sparsification of Directed Hypergraphs (in session "Track A-4")

Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems (in session "Track A-1")

Network Satisfaction Problems Solved by k-Consistency (in session "Track B")

New Additive Emulators (in session "Track A-2")

New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling (in session "Track A-1")

New PRGs for Unbounded-width/Adaptive-order Read-once Branching Programs (in session "Track A-4")

Nominal Topology for Data Languages (in session "Track B")

Nondeterministic Refutations for Nearest Boolean Vector (in session "Track A-3")

On computing the vertex connectivity of 1-plane graphs (in session "Track A-1")

On Differentially Private Counting on Trees (in session "Track A-3")

On Finding Constrained Independent Sets in Cycles (in session "Track A-4")

On Range Summary Queries (in session "Track A-3")

On Semantically-Deterministic Automata (in session "Track B")

On Sparsification of Stochastic Packing Problems (in session "Track A-3")

On the complexity of diameter and related problems in permutation groups (in session "Track B")

On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete $k$-Center for Small $k$ (in session "Track A-2")

On the Limits of Decision: the Adjacent Fragment of First-Order Logic (in session "Track B")

On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n) (in session "Track A-3")

Online Demand Scheduling with Failovers (in session "Track A-2")

Opening Address

Opening Speech for the 50th ICALP Anniversary Session (in session "50th ICALP Anniversary Session")

Optimal (degree+1)-Coloring in Congested Clique (in session "Track A-2")

Optimal Adjacency Labels for Subgraphs of Cartesian Products (in session "Track A-3")

Optimal Decremental Connectivity in Non-Sparse Graphs (in session "Track A-1")

Ortho-radial Drawing in Near-linear Time (in session "Track A-2")

Parallel algorithms strike back (in session "Colloquium in honor of Friedhelm Meyer auf der Heide")

Parallel self-testing of EPR pairs under computational assumptions (in session "Track A-2")

Parameter estimation for Gibbs distributions (in session "Track A-3")

Parameterised and Fine-grained Subgraph Counting, modulo 2 (in session "Track A-2")

Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters (in session "Track A-2")

Population Protocols with Unordered Data (in session "Track B")

Positivity Problems for Reversible Linear Recurrence Sequences (in session "Track B")

Presburger Award 2023 (in session "Presburger & Church Award Talks")

Presburger Award 2023 (in session "Presburger & Church Award Talks")

Probabilistic Guarded KAT Modulo Bisimilarity: Completeness and Complexity (in session "Track B")

Protecting Single-Hop Radio Networks from Message Drops (in session "Track A-2")

Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints (in session "Track A-1")

Quantum codes, local testability and interactive proofs: state of the art and open questions (in session "Keynote talk")

Quantum cryptography with classical communication - Parallel remote state preparation for copy-protection, verification, and more (in session "Track A-2")

Regular Methods for Operator Precedence Languages (in session "Track B")

Rerouting Planar Curves and Disjoint Paths (in session "Track A-2")

Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation (in session "Track A-4")

Sample-based distance-approximation for subsequence-freeness (in session "Track A-3")

Scheduling under Non-Uniform Job and Machine Delays (in session "Track A-3")

Searching for Regularity in Bounded Functions (in session "Track A-4")

Simulating Markovian open quantum systems using higher-order series expansion (in session "Track A-1")

Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching (in session "Track A-2")

Stable Matching: Choosing Which Proposals to Make (in session "Track A-1")

Streaming $k$-edit approximate pattern matching via string decomposition (in session "Track A-4")

Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics (in session "Track A-4")

Sublinear Algorithms for the Analysis of very large graphs (in session "Colloquium in honor of Friedhelm Meyer auf der Heide")

Sublinear Time Eigenvalue Approximation via Random Sampling (in session "Track A-4")

The Communication Complexity of Set Intersection under Product Distributions (in session "Track A-4")

The complexity of Presburger arithmetic with power or powers (in session "Track B")

The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems (in session "Track B")

The Geometry of Tree-Based Sorting (in session "Track A-2")

The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Cross-Model Simulation in Tile-Based Self-Assembly (in session "Track A-4")

The Skolem Landscape (in session "Keynote talk")

The Support of Open versus Closed Random Walks (in session "Track A-3")

The wrong direction of Jensen’s inequality is algorithmically right (in session "Track A-3")

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth (in session "Track A-2")

Triangle Counting with Local Edge Differential Privacy (in session "Track A-3")

Truthful Matching with Online Items and Offline Agents (in session "Track A-1")

Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar (in session "Track A-2")

Universal hashing, sequential and parallel and fast (most of the time) (in session "Colloquium in honor of Friedhelm Meyer auf der Heide")

Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting (in session "Track B")

Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery (in session "Track A-3")

Include materials from selected contributions

Events scheduled on*

7/10/23

7/11/23

7/12/23

7/13/23

7/14/23

Include materials from sessions/contributions scheduled on the selected dates