ICALP 2023 - Call for Participation
========================================================
The 50th EATCS International Colloquium on Automata, Languages, and Programming
(ICALP) will take place in:
Paderborn, Germany, on 10-14 July 2023.
ICALP is the main conference and annual meeting of the European
Association for Theoretical Computer Science (EATCS). As usual, ICALP will
be preceded by a series of workshops, which will take place on July 10.
The 2023 edition has the following features:
- The conference is planned as a physical, in-person event.
- This will be the 50th ICALP conference and some special events are planned.
========================================================
Important dates and information
========================================================
Conference website: https://icalp2023.cs.upb.de/
Twitter: @ICALPconf
Conference: July 10-14, 2023 (Workshops on July 10, 2023)
========================================================
Registration
========================================================
Please register here: https://icalp2023.cs.upb.de/registration/
On-site child care:
Please contact noelle.maicher.hoff@upb.de of the Equality Office of Paderborn University as soon as possible.
========================================================
Invited Speakers
========================================================
Anna Karlin - University of Washington, USA
Rasmus Kyng - ETH Zurich, Switzerland
Rupak Majumdar - Max Planck Institute for Software Systems, Germany
Thomas Vidick - California Institute of Technology, USA, and Weizmann Institute of Science, Israel
James Worrell - University of Oxford, UK
Special 50th ICALP session:
Kurt Mehlhorn (MPI für Informatik, Saarland Informatics Campus)
Thomas Henzinger (IST Austria)
========================================================
Awards
========================================================
EATCS Award 2023
----------------
Amos Fiat
Church Award
------------
Ralf Jung, David Swasey, Filip Sieczkowski, Kasper Svendsen, Aaron Turon, Lars Birkedal, Derek Dreyer: "Iris: Monoids and Invariants as an Orthogonal Basis for Concurrent Reasoning". POPL 2015.
Ralf Jung, Robbert Krebbers, Lars Birkedal, Derek Dreyer: "Higher-order ghost state". ICFP 2016.
Robbert Krebbers, Ralf Jung, Aleš Bizjak, Jacques-Henri Jourdan, Derek Dreyer, Lars Birkedal: "The Essence of Higher-Order Concurrent Separation Logic". ESOP 2017.
Ralf Jung, Robbert Krebbers, Jacques-Henri Jourdan, Aleš Bizjak, Lars Birkedal, Derek Dreyer: "Iris from the ground up: A modular foundation for higher-order concurrent separation logic". J. Funct. Program. 28 (2018)
Presburger Award 2023
---------------------
Aaron Bernstein
Thatchaphol Saranurak
EATCS Distinguished Dissertation Award for 2022
-----------------------------------------------
Kuikui Liu: "Spectral Independence: A New Tool to Analyze Markov Chains" (University of Washington; supervisor: Shayan Oveis Gharan).
Alex Lombardi: "Provable Instantiations of Correlation Intractability and the Fiat-Shamir Heuristic" (Electrical Engineering and Computer Science (EECS) at MIT; supervisor: Vinod Vaikuntanathan)
Lijie Chen: "Better Hardness via Algorithms, and New Forms of Hardness versus Randomness" (MIT Department of Electrical Engineering and Computer Science; supervisor: Ryan Williams)
Best Paper Award
----------------
Track A: Online Learning and Disambiguations of Partial Concept Classes (Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami and Kaave Hosseini)
Track A: A 4/3 Approximation for 2-Vertex-Connectivity (Miguel Bosch Calvo, Fabrizio Grandoni and Afrouz Jabal Ameli)
Track B: Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality (Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks and Karol Węgrzycki)
Best Student Paper Award
------------------------
Track A: Minimum Chain Cover in Almost Linear Time (Manuel Cáceres)
Track B: The Identity Problem in $\mathbb{Z}\wr\mathbb{Z}$ is decidable (Ruiwen Dong)
=========================================================
Workshops
=========================================================
See https://icalp2023.cs.upb.de/workshops/ for more information.
- Combinatorial Reconfiguration
- Graph Width Parameters: from Structure to Algorithms (GWP 2023)
- Algorithmic Aspects of Temporal Graphs VI
- 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!
- Algebraic Complexity Theory
- Computer Science for CONTINUOUS Data
=========================================================
Accepted papers
=========================================================
//////////////////////
TRACK A
//////////////////////
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi and Kewen Wu. On Differentially Private Counting on Trees
Leslie Ann Goldberg and Marc Roth. Parameterised and Fine-grained Subgraph Counting, modulo 2
Michał Wlodarczyk. Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
Laure Morelle, Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos. Faster parameterized algorithms for modification problems to minor-closed classes
Sanjeev Khanna, Yu Chen and Zihan Tan. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics
Noam Touitou. Frameworks for Nonclairvoyant Network Design with Deadlines or Delay
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shunichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki. Rerouting Planar Curves and Disjoint Paths
Honghao Fu, Daochen Wang and Qi Zhao. Parallel self-testing of EPR pairs under computational assumptions
Shi Li. Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems
Shyan Akmal and Ce Jin. An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan and Laszlo Kozma. Fast approximation of search trees on trees with centroid trees
Ishan Bansal, Joe Cheriyan, Logan Grout and Sharat Ibrahimpur. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
Hadley Black, Iden Kalemaj and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing
Claire Mathieu and Hang Zhou. A Tight $(1.5+\epsilon)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees
Sixue Liu, Zhao Song, Hengjie Zhang, Lichen Zhang and Tianyi Zhou. Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
Spencer Compton, Slobodan Mitrović and Ronitt Rubinfeld. New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling
Tatsuya Terao. Faster Matroid Partition Algorithms
David Harris and Vladimir Kolmogorov. Parameter estimation for Gibbs distributions
Eric Rivals, Michelle Sweering and Pengfei Wang. Convergence of the number of period sets in strings
David E. Roberson and Tim Seppelt. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann and Leon Schiller. Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
Konstantina Mellou, Marco Molinaro and Rudy Zhou. Online Demand Scheduling with Failovers
David Eppstein and Daniel Frishberg. Improved mixing for the convex polygon triangulation flip walk
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco and Archan Ray. Sublinear Time Eigenvalue Approximation via Random Sampling
Lijie Chen, Xin Lyu, Avishay Tal and Hongxun Wu. New PRGs for Unbounded-width/Adaptive-order Read-once Branching Programs
Petr Hlineny and Jan Jedelský. Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar
Yann Disser, Max Klimm, Kevin Schewior and David Weckbecker. Incremental Maximization via Continuization
Mohit Garg, Felix Hommelsheim and Nicole Megow. Matching Augmentation via Simultaneous Contractions
Manuel Cáceres. Minimum Chain Cover in Almost Linear Time
Zachary Friggstad and Ramin Mousavi. An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs
Shu Liu, Chaoping Xing and Chen Yuan. List Decoding of Rank-Metric Codes with Row-to-Column Ratio Bigger Than 1/2
Yossi Azar and Danny Vainstein. Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering
Daniel Hader and Matthew Patitz. The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Cross-Model Simulation in Tile-Based Self-Assembly
Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
Ishan Agarwal and Richard Cole. Stable Matching: Choosing Which Proposals to Make
Ruizhe Zhang and Xinzhi Zhang. A Hyperbolic Extension of Kadison-Singer Type Results
Fedor Fomin, Petr Golovach, Danil Sagunov and Kirill Simonov. Approximating Long Cycle Above Dirac's Guarantee
Michael Whitmeyer and Siddharth Iyer. Searching for Regularity in Bounded Functions
Vaishali Surianarayanan, Daniel Lokshtanov and Saket Saurabh. Breaking the All Subsets Barrier for Min $k$-Cut
Magdalen Dobson and Guy Blelloch. The Geometry of Tree-Based Sorting
Thiago Bergamaschi. Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians
Shaddin Dughmi, Yusuf Hakan Kalaycı and Neel Patel. On Sparsification of Stochastic Packing Problems
Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves under Frechet Distance
Gramoz Goranci and Monika Henzinger. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow
Shimon Kogan and Merav Parter. New Additive Emulators
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann and Martin Schirneck. Fault-Tolerant ST-Diameter Oracles
Michal Feldman, Federico Fusco, Simon Mauras and Rebecca Reiffenhäuser. Truthful Matching with Online Items and Offline Agents
Ilan Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation
Fedor Fomin, Petr Golovach, Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos. Compound Logics for Modification Problems
Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter Rasmussen and Mikkel Thorup. Optimal Decremental Connectivity in Non-Sparse Graphs
Dana Ron and Omer Cohen Sidon. Sample-based distance-approximation for subsequence-freeness
Siddharth Barman and Pooja Kulkarni. Approximation Algorithms for Envy-Free Cake Division with Connected Pieces
Kazusato Oko, Shinsaku Sakaue and Shin-ichi Tanigawa. Nearly Tight Spectral Sparsification of Directed Hypergraphs
Daniel Agassy, Dani Dorfman and Haim Kaplan. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
Jakob Bæk Tejs Houen and Mikkel Thorup. A Sparse Johnson-Lindenstrauss Transform using Fast Hashing
Pan Peng and Yuyang Wang. An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs
Minglong Qin and Penghui Yao. Decidability of fully quantum nonlocal games with noisy maximally entangled states
Louis Esperet, Nathaniel Harms and Viktor Zamaraev. Optimal Adjacency Labels for Subgraphs of Cartesian Products
Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi and Jukka Suomela. Locality in online, dynamic, sequential, and distributed graph algorithms
Dmitry Paramonov, Gillat Kol, Klim Efremenko and Raghuvansh R. Saxena. Protecting Single-Hop Radio Networks from Message Drops
Alexandru Gheorghiu, Tony Metger and Alexander Poremba. Quantum cryptography with classical communication - Parallel remote state preparation for copy-protection, verification, and more
Andrzej Dorobisz and Jakub Kozik. Local Computation Algorithms for Hypergraph Coloring - following Beck's approach
Ishay Haviv. On Finding Constrained Independent Sets in Cycles
Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser and Malin Rau. Dynamic Averaging Load Balancing on Arbitrary Graphs
Ilan Doron, Ariel Kulik and Hadas Shachnai. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
Karthik Murali and Therese Biedl. On computing the vertex connectivity of 1-plane graphs
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan and Shay Sapir. Lower Bounds for Pseudo-Deterministic Counting in a Stream
Charilaos Efthymiou and Weiming Feng. On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n)
Jun-Ting Hsieh and Pravesh K Kothari. Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
Or Zamir. The wrong direction of Jensen's inequality is algorithmically right
Talya Eden, Sofya Raskhodnikova, Quanquan C. Liu and Adam Smith. Triangle Counting with Local Edge Differential Privacy
Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt and Julian Wargalla. Connected k-Center and k-Diameter Clustering
Dylan Hyatt-Denesik, Afrouz Ameli and Laura Sanita. Finding Almost Tight Witness Trees
Adam Karczmarz and Piotr Sankowski. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs
Xiantao Li and Chunhao Wang. Simulating Markovian open quantum systems using higher-order series expansion
Monika Henzinger, Paul Liu, Jan Vondrák and Da Wei Zheng. Faster submodular maximization for several classes of matroids
Miguel Bosch Calvo, Fabrizio Grandoni and Afrouz Jabal Ameli. A 4/3 Approximation for 2-Vertex-Connectivity
Paul Beame and Niels Kornerup. Cumulative Memory Lower Bounds for Randomized and Quantum Computation
Sudatta Bhattacharya and Michal Koucky. Streaming $k$-edit approximate pattern matching via string decomposition
Robert Ferens and Marek Szykuła. Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds
David Stalfa, Rajmohan Rajaraman and Sheng Yang. Scheduling under Non-Uniform Job and Machine Delays
Konstantinos Zampetakis and Charilaos Efthymiou. Broadcasting with Random Matrices
Chandra Chekuri and Rhea Jain. Approximation Algorithms for Network Design in Non-Uniform Fault Models
Jin-Yi Cai and Ben Young. Planar \#CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint
Andrej Bogdanov and Alon Rosen. Nondeterministic Refutations for Nearest Boolean Vector
Amir Azarmehr and Soheil Behnezhad. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation
Timothy M. Chan, Qizheng He and Yuancheng Yu. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete $k$-Center for Small $k$
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami and Kaave Hosseini. Online Learning and Disambiguations of Partial Concept Classes
Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee and Joshua Wang. Efficient Caching with Reserves via Marking
Jun-Ting Hsieh, Pravesh Kothari, Aaron Potechin and Jeff Xu. Ellipsoid Fitting Up to a Constant
Ryu Hayakawa, Jordi Weggemans, Tomoyuki Morimae, Chris Cade, Marten Folkertsma, Sevag Gharibian and Francois Le Gall. Improved Hardness Results for the Guided Local Hamiltonian Problem
Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar and Ashish Goel. Low Sample Complexity Participatory Budgeting
Yi-Jun Chang. Ortho-radial Drawing in Near-linear Time
Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei and Yu Zheng. Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes
Rotem Oshman and Tal Roth. The Communication Complexity of Set Intersection under Product Distributions
Thomas Sauerwald, He Sun and Danny Vagnozzi. The Support of Open versus Closed Random Walks
Sam Coy, Artur Czumaj, Peter Davies and Gopinath Mishra. Optimal (degree+1)-Coloring in Congested Clique
Ittai Rubinstein. Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha and Bhargav Thankey. Low-depth arithmetic circuit lower bounds: Bypassing set-multilinearization
Nicolas Resch, Chen Yuan and Yihan Zhang. Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery
Peyman Afshani, Pingan Cheng, Aniket Basu Roy and Zhewei Wei. On Range Summary Queries
//////////////////////
TRACK B
//////////////////////
Frits Vaandrager and Thorsten Wißmann. Action Codes
Michael Lampis. First Order Logic on Pathwidth Revisited Again
Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour and Pierre Vandenhove. How to Play Optimally for Regular Objectives?
Bader Abu Radi and Orna Kupferman. On Semantically-Deterministic Automata
Manuel Bodirsky and Simon Knäuer. Network Satisfaction Problems Solved by k-Consistency
Ruiwen Dong. The Identity Problem in $\mathbb{Z} \wr \mathbb{Z}$ is decidable
Michael Blondin and François Ladouceur. Population Protocols with Unordered Data
Markus Lohrey and Andreas Rosowski. On the complexity of diameter and related problems in permutation groups
Moritz Lichter. Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting
Wojciech Rozowski, Tobias Kappé, Dexter Kozen, Todd Schmid and Alexandra Silva. Probabilistic Guarded KAT Modulo Bisimilarity: Completeness and Complexity
Bartosz Bednarczyk, Ian Pratt-Hartmann and Daumantas Kojelis. On the of Limits of Decision: the Adjacent Fragment of First-Order Logic
Mikołaj Bojańczyk and Lê Thành Dũng Nguyễn. Algebraic Recognition of Regular Functions
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz and Szymon Toruńczyk. Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes
Antonio Casares and Pierre Ohlmann. Characterising memory in infinite games
Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski and Szymon Toruńczyk. Canonical decompositions in monadically stable and bounded shrubdepth graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski and Szymon Toruńczyk. Flipper games for monadically stable graph classes
Titouan Carette, Etienne Moutot, Thomas Perez and Renaud Vilmart. Compositionality of planar perfect matchings, a universal and complete fragment of ZW-calculus
Harry Vinall-Smeeth and Christoph Berkholz. A dichotomy for succinct representations of homomorphisms
Javier Esparza and Vincent Grande. Black-box Testing Liveness Properties of Partially Observable Stochastic Systems
Thomas Henzinger, Pavol Kebis, Nicolas Mazzocchi and N. Ege Saraç. Regular Methods for Operator Precedence Languages
George Kenison, Joris Nieuwveld, Joël Ouaknine and James Worrell. Positivity Problems for Reversible Linear Recurrence Sequences
Olivier Carton, Gaëtan Douéneau-Tabot, Emmanuel Filiot and Sarah Winter. Deterministic regular functions of infinite words
Fabian Birkmann, Stefan Milius and Henning Urbat. Nominal Topology for Data Languages
Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks and Karol Węgrzycki. Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality
Austen Z. Fan, Paraschos Koutris and Hangdong Zhao. The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems
Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar and Kuldeep Meel. Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle?
Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis and Aris Papadopoulos. Monadic NIP in monotone classes of relational structures
Michael Benedikt, Dmitry Chistikov and Alessio Mansutti. The complexity of Presburger arithmetic with power or powers
Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan Thinniyam Srinivasan and Georg Zetzsche. Checking Refinement of Asynchronous Programs against Context-Free Specifications
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
