[TYPES/announce] ICALP 2024 - Call for Participation
Pawel Sobocinski
sobocinski at gmail.com
Mon May 13 05:01:22 EDT 2024
========================================================
ICALP 2024 - Call for Participation
========================================================
**** early registration ends May 17 2024! ****
The 51st EATCS International Colloquium on Automata, Languages, and Programming
(ICALP) will take place in:
Tallinn, Estonia, on 8-12 July 2024.
ICALP is the main conference and annual meeting of the European
Association for Theoretical Computer Science (EATCS).
The 2024 edition of ICALP is colocated with LiCS (8-11 July, https://urldefense.com/v3/__https://lics.siglog.org/lics24/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp5qugfvkw$ )
and FSCD (10-13 July, https://urldefense.com/v3/__https://cs.ioc.ee/fscd24/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp6gzqVUKA$ )
Conference website: https://urldefense.com/v3/__https://compose.ioc.ee/icalp2024/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7pRN5iRQ$
Local organisation enquiries: icalp_lics_fscd2024 at taltech.ee
========================================================
Registration
========================================================
Early registration: *** May 17, 2024 by 23:59 EET ***
Register here: https://urldefense.com/v3/__https://compose.ioc.ee/icalp2024/*registration__;Iw!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7B-_4yhw$
========================================================
Invited Speakers
========================================================
Edith Elkind, University of Oxford
Stephanie Weirich, University of Pennsylvania
Anuj Dawar, University of Cambridge
Danupon Nanongkai, MPI Saarbrücken
Merav Parter, Weizmann Institute
=== LiCS invited speakers ===
Martin Escardó, University of Birmingham
Alexandra Silva, Cornell University
=== LiCS invited tutorial speakers ===
Sam Buss, UCSD
Alex Simpson, University of Ljubljana
=== FSCD invited speakers 2
Delia Kesner, Université Paris Cité
Bettina Könighofer, TU Graz
Sebastian Ullrich, LEAN-FRO
========================================================
Awards
========================================================
During the conference, the following awards will be given:
– the Gödel prize (https://urldefense.com/v3/__https://eatcs.org/index.php/goedel-prize__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp69w9lOLQ$ ),
– the EATCS award (https://urldefense.com/v3/__https://eatcs.org/index.php/eatcs-award__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp4sLho0JA$ ),
– the Presburger award (https://urldefense.com/v3/__https://eatcs.org/index.php/presburger__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp51SN_1zQ$ ),
– the EATCS distinguished dissertation award (https://urldefense.com/v3/__https://eatcs.org/index.php/dissertation-award__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp4S2koMwQ$ ),
– the best papers for Track A and Track B,
– the best student papers for Track A and Track B (see submission guidelines).
=========================================================
ICALP/LiCS/FSCD Workshops
=========================================================
- Algorithmic Aspects of Temporal Graphs VII (AATG 2024), 7 July 2024,
https://urldefense.com/v3/__https://mertzios.net/Workshops/ICALP-24-Satellite/Temporal-Graphs-ICALP-2024.html__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7GxUkNsg$
- Geometric and Topological Methods in Computer Science (GETCO 2024), 6-7 July 2024,
https://urldefense.com/v3/__https://getco-conf.github.io/2024/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp4VXgIiwg$
- Intersection Types and Related Systems (ITRS 2024), 9 July 2024,
https://urldefense.com/v3/__https://itrs.di.unito.it/index.html__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp43Ki3kMg$
- International Workshop on Confluence (IWC 2024), 9 July 2024,
https://urldefense.com/v3/__https://www.trs.css.i.nagoya-u.ac.jp/event/iwc2024/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp5ivhtBRw$
- Learning and Automata (LearnAut 2024), 7 July 2024,
https://urldefense.com/v3/__https://learnaut2024.github.io/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp6Jm0Dq4A$
- Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2024), 8 July 2024,
https://urldefense.com/v3/__https://lfmtp.github.io/lfmtp-page/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7EvxOJJQ$
- Logic Mentoring Workshop (LMW 2024), 7 July 2024,
https://urldefense.com/v3/__https://logic-mentoring-workshop.github.io/lics24/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp4fyIgtOA$
- Mathematically Structured Functional Programming (MSFP 2024), 8 July 2024,
https://urldefense.com/v3/__https://msfp-workshop.github.io/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp5fs4ExXQ$
- Parameterized Approximation Algorithms Workshop (PAAW 2024), 6 July 2024,
https://urldefense.com/v3/__https://sites.google.com/site/aefeldmann/workshop/2024__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7tNtmL4g$
- Parameterized Algorithms and Constraint Satisfaction (PACS 2024), 7 July 2024,
https://urldefense.com/v3/__https://pacs2024.github.io/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp6qbq0LhA$
- Structure meets Power (SmP 2024), 7 July 2024,
https://urldefense.com/v3/__https://www.cst.cam.ac.uk/conference/structure-meets-power-2024__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp78EVb3rg$
- Trends in Arithmetic Theories (TAT 2024), 6 July 2024,
https://urldefense.com/v3/__https://www.cs.ox.ac.uk/people/christoph.haase/home/trends-24/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp4D0Bda0w$
- Eighth International Workshop on Trends in Linear Logic and
Applications (TLLA 2024), 8-9 July 2024,
https://urldefense.com/v3/__https://lipn.univ-paris13.fr/TLLA/2024/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7S3-Itmg$
- Women in Logic 2024, 9 July 2024,
https://urldefense.com/v3/__https://womeninlogic.org/__;!!IBzWLUs!UBXsU3RwTtj9r3h5PtDa-R0qQTGM1LZQ2odgQ2fS6TBe3aoxfDY5jzh9yTg4D9ahhkH9hwmy-78ZbISXrb-fzE-Yqp7es-o-Pg$
============= Accepted papers =============
=== TRACK A ===
Marin Bougeret, Bart M. P. Jansen and Ignasi Sau. Kernelization Dichotomies
for Hitting Subgraphs under Structural Parameterizations
Ce Jin and Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums
Hamed Hatami, Kaave Hosseini, Shachar Lovett and Anthony Ostuni.
Refuting approaches to the log-rank conjecture for XOR functions
Yiannis Giannakopoulos, Alexander Grosz and Themistoklis Melissourgos.
On the Smoothed Complexity of Combinatorial Local Search
Yu Chen and Zihan Tan. Lower Bounds on 0-Extension with Steiner Nodes
Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk and Paweł Rzążewski.
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth
via Asymptotic Matrix Parameters
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach and
Tuukka Korhonen. Two-sets cut-uncut on planar graphs
Shiri Chechik, Doron Mukhtar and Tianyi Zhang. Streaming Edge Coloring with
Subquadratic Palette Size
Shiri Chechik and Tianyi Zhang. Path-Reporting Distance Oracles with Logarithmic
Stretch and Linear Size
Guy Goldberg. Linear Relaxed Locally Decodable and Correctable Codes Do Not Need
Adaptivity and Two-Sided Error
Soh Kumabe and Yuichi Yoshida. Lipschitz Continuous Allocations for Optimization Games
Junjie Chen, Minming Li, Haifeng Xu and Song Zuo. Bayesian Calibrated Click-Through Auctions
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx and Roohani Sharma. Subexponential
Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General
Matroid Constraint
Jonas Kamminga and Sevag Gharibian. BQP, meet NP: Search-to-decision reductions
and approximate counting
William Kuszmaul and Zoe Xi. Towards an Analysis of Quadratic Probing
Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems
Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider
and Simon Weber. Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
Andreas Emil Feldmann and Michael Lampis. Parameterized Algorithms for Steiner Forest
in Bounded Width Graphs
Sophia Heimann, Hung P. Hoang and Stefan Hougardy. The k-Opt algorithm for the Traveling
Salesman Problem has exponential running time for k > 5
Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-mincut: Efficient Algorithms,
Compact Structures, & Optimal Sensitivity Oracles
Mario Grobler, Stephanie Maaz, Nicole Megow, Amer Mouawad, Vijayaragunathan Ramamoorthi,
Daniel Schmand and Sebastian Siebertz.
Solution discovery via reconfiguration for problems in P
Sanjeev Khanna, Aaron Putterman and Madhu Sudan.
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings
Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen and Tomáš Masařík.
Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor
Ce Jin, Michael Kapralov, Sepideh Mahabadi and Ali Vakilian.
Streaming Algorithms for Connectivity Augmentation
Orestis Plevrakis, Seyoon Ragavan and S. Matthew Weinberg.
On the cut-query complexity of approximating max-cut
Klaus Heeger, Danny Hermelin, Matthias Mnich and Dvir Shabtay.
No Polynomial Kernels for Knapsack
Itai Boneh, Shay Golan, Shay Mozes and Oren Weimann.
Õptimal Dynamic Time Warping on Run-Length Encoded Strings
Shuichi Hirahara and Naoto Ohsaka.
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
Shiri Chechik and Tianyi Zhang.
Faster Algorithms for Dual-Failure Replacement Paths
Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang and Yuhao Zhang.
Algorithms for the Generalized Poset Sorting Problem
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek
and Sorrachai Yingchareonthawornchai.
The Group Access Bounds for Binary Search Trees
Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu
and Adrian Vetta. Robot positioning using torus packing for multisets
Christophe Paul, Evangelos Protopapas, Dimitrios Thilikos
and Sebastian Wiederrecht.
Delineating Half-Integrality of the Erdős-Pósa Property for Minors:
the Case of Surfaces
Agastya Vibhuti Jha and Akash Kumar.
A Sublinear Time Tester for Max-Cut on Clusterable Graphs
Yotam Kenneth and Robert Krauthgamer.
Cut Sparsification and Succinct Representation of Submodular Hypergraphs
Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser,
Daniel Schmand and Giovanna Varricchio.
Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin
and Stéphan Thomassé.
Vertex-minor universal graphs for generating entangled quantum subsystems
Augusto Modanese and Yuichi Yoshida.
Testing Spreading Behavior in Networks with Arbitrary Topologies
Matan Gilboa. A Characterization of Complexity in Public Goods Games
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király and Shubhang Kulkarni.
Splitting-off in Hypergraphs
Sariel Har-Peled, Elfarouk Harb and Vasilis Livanos.
Oracle-Augmented Prophet Inequalities
Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović, Krzysztof Onak and Piotr Sankowski.
Dynamic PageRank: Algorithms and Lower Bounds
Emile Anand, Jan van den Brand, Mehrdad Ghadiri and Daniel J Zhang.
The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
Yury Makarychev, Max Ovsiankin and Erasmo Tani.
Approximation Algorithms for lp-Shortest Path and lp-Group Steiner Tree
Adam Karczmarz and Marcin Smulewicz.
Fully Dynamic Strongly Connected Components in Planar Digraphs
Shyan Akmal, Virginia Vassilevska Williams and Nicole Wein.
Detecting Disjoint Shortest Paths in Linear Time and More
Kingsley Yung. Limits of Sequential Local Algorithms on the Random k-XORSAT Problem
Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo and Jiaheng Wang.
Approximate counting for spin systems in sub-quadratic time
Chiranjib Bhattacharyya, Ravindran Kannan and Amit Kumar.
Random Separating Hyperplane Theorem and Learning Polytopes
Michal Dory, Sebastian Forster, Yasamin Nazari and Tijn de Vos.
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Vikraman Arvind and Pushkar Joglekar.
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
Shuangle Li, Bingkai Lin and Yuwei Liu.
Improved Lower Bounds for Approximating Parameterized Nearest
Codeword and Related Problems under ETH
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer and Pavel Veselý.
Fully-Scalable MPC Algorithms for Clustering in High Dimension
Clément Dallard, Fedor Fomin, Petr Golovach, Tuukka Korhonen and Martin Milanič.
Computing Tree Decompositions with Small Independence Number
Andreas Björklund, Petteri Kaski and Jesper Nederlof.
Another Hamiltonian cycle in bipartite Pfaffian graphs
Johannes Meintrup, Frank Kammer, Konstantinos Dogeas, Thomas Erlebach
and William K. Moses Jr..
Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
Yossi Azar, Shahar Lewkowicz and Danny Vainstein.
List Update with Delays or Time Windows
Boris Klemz and Marie Diana Sieper.
Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
Weiming Feng and Heng Guo.
An FPRAS for two terminal reliability in directed acyclic graphs
Martin Grohe and Daniel Neuen. Isomorphism for Tournaments of Small Twin Width
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi,
Kevin Yeo and Or Zamir.
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani
and Mateusz Rychlicki. A Tight Subexponential Algorithm for Two-Page Book Embedding
Baris Can Esmer, Jacob Focke, Dániel Marx and Paweł Rzążewski.
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams.
Fast Approximate Counting of Cycles
Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka
and Ayumi Shinohara.
Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg and Sushant Sachdeva.
Optimal Electrical Oblivious Routing on Expanders
Shi Li, Chenyang Xu and Ruilong Zhang.
Polylogarithmic Approximations for Robust s-t Path
Kent Quanrud. Adaptive sparsification for matroid intersection
Sushant Sachdeva, Anvith Thudi and Yibin Zhao.
Better Sparsifiers for Directed Eulerian Graphs
Yuda Feng and Shi Li.
A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
Niklas Schlomberg. An improved integrality gap for disjoint cycles in planar graphs
Reut Levi, Talya Eden and Dana Ron. Testing Ck-freeness in bounded-arboricity graphs
Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta and Saswata Mukherjee.
Exponential lower bounds via exponential sums
Ariel Korin, Tsvi Kopelowitz and Liam Roditty.
On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
Noga Ron-Zewi and Elie Abboud.
Finer-grained Reductions in Fine-grained Hardness of Approximation
Ilan Doron-Arad, Ariel Kulik and Hadas Shachnai.
Lower Bounds for Matroid Optimization Problems with a Linear Constraint
Vladimir Podolskii and Dmitrii Sluch.
One-Way Communication Complexity of Partial XOR Functions
Fateme Abbasi, Marek Adamczyk, Miguel Bosch Calvo, Jarosław Byrka,
Fabrizio Grandoni, Krzysztof Sornat and Antoine Tinguely.
An O(loglog n)-Approximation for Submodular Facility Location
Lucas Gretta and Eric Price.
Sharp Noisy Binary Search with Monotonic Probabilities
Aditi Dudeja. Decremental Matching in General Weighted Graphs
Djamal Belazzougui, Gregory Kucherov and Stefan Walzer.
Better space-time-robustness trade-offs for set reconciliation
Sami Davies, Benjamin Moseley and Heather Newman.
Simultaneously Approximating All lp-norms in Correlation Clustering
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein and Amin Saberi.
Sublinear Algorithms for TSP via Path Covers
Holger Dell, John Lapinskas and Kitty Meeks.
Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Leonid Gurvits, Nathan Klein and Jonathan Leake.
>From Trees to Polynomials and Back Again: New Capacity Bounds with
Applications to TSP
Shalev Ben-David and Srijita Kundu.
Oracle separation of QMA and QCMA with bounded adaptivity
Prantar Ghosh and Manuel Stoeckl. Low-Memory Algorithms for Online Edge Coloring
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj and
Ramanujan M. Sridharan.
Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Mónika Csikós and Nabil Mustafa.
An Optimal Sparsification Lemma for Low-Crossing Matchings and its Applications
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev and Maksim Zhukovskii.
Tight Bounds on Adjacency Labels for Monotone Graph Classes
Mohammad Hossein Bateni, Laxman Dhulipala, Kishen Gowda, D Ellis Hershkowitz,
Rajesh Jarayam and Jakub Lacki.
Parallel and Sequential Hardness of Hierarchical Graph Clustering
Eunou Lee and Ojas Parekh. An improved Quantum Max Cut approximation via Maximum Matching
Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney,
Roohani Sharma and Prafullkumar Tale.
Problems in NP can Admit Double-Exponential Lower Bounds when
Parameterized by Treewidth and Vertex Cover
Soheil Behnezhad and Mohammad Saneian.
Streaming Edge Coloring with Asymptotically Optimal Colors
Jan Olkowski, Dariusz Kowalski and Mohammad Hajiaghayi.
Distributed fast crash-tolerant consensus with nearly-linear quantum communication
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay and Chen Wang.
The Discrepancy of Shortest Paths
Charlie Carlson, Ewan Davies, Alexandra Kolla and Aditya Potukuchi.
A spectral approach to approximately counting independent sets in dense bipartite graphs
Xin Li and Yan Zhong. Two-Source and Affine Non-Malleable Extractors for Small Entropy
Omkar Baraskar, Agrim Dewan, Chandan Saha and Pulkit Sinha.
NP-hardness of testing equivalence to sparse polynomials and constant support polynomials
Yaowei Long and Yunfan Wang.
Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
Noel Arteche, Erfan Khaniki, Ján Pich and Rahul Santhanam.
>From Proof Complexity to Circuit Complexity via Interactive Protocols
Kevin Hua, Daniel Li, Jaewoo Park and Thatchaphol Saranurak.
Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein and Zixuan Xu.
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Zhenjian Lu and Rahul Santhanam.
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity
Panagiotis Charalampopoulos, Pawel Gawrychowski and Samah Ghazawi.
Optimal Bounds for Distinct Quartics
Ilan Doron and Seffi Naor. Non-Linear Paging
Narek Bojikian and Stefan Kratsch.
A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
Yasushi Kawase, Koichi Nishimura and Hanna Sumita.
Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets
Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal and Andreas Wiese.
Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
Srnivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez and Carlos Palazuelos.
Learning low-degree quantum objects
Nick Fischer and Leo Wennmann.
Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki and Tamás Schwarcz.
Problems on Group-labeled Matroid Bases
Fateme Abbasi, Sandip Banerjee, Joachim Spoerhase, Ameet Gadekar, Roohani Sharma,
Jaroslaw Byrka, Kamyar Khodamoradi, Parinya Chalermsook and Dániel Marx.
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Serge Gaspers and Jerry Zirui Li.
Quantum Algorithms for Graph Coloring and other Partitioning, Covering,
and Packing Problems
Yu Chen, Michael Kapralov, Mikhail Makarov and Davide Mazzali.
On the Streaming Complexity of Expander Decomposition
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh
and Anannya Upasana.
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Aaron Potechin and Aaron Zhang.
Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle
=== TRACK B ===
Sylvain Schmitz and Lia Schütze.
On the Length of Strongly Monotone Descending Chains over ℕᵈ
Alberto Larrauri and Stanislav Živný.
Solving promise equations over monoids and groups
Massimo Benerecetti, Laura Bozzelli, Fabio Mogavero and Adriano Peron.
Automata-Theoretic Characterisations of Branching-Time Temporal Logics
George Kenison.
The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters
Mohan Sai Teja Dantam and Richard Mayr.
Finite-memory Strategies for Almost-sure Energy-MeanPayoff Objectives in MDPs
Guillaume Theyssier. FO logic on cellular automata orbits equals MSO logic
Yuxi Fu, Qizhe Yang and Yangluo Zheng. Improved Algorithm for Reachability in d-VASS
Julian Dörfler and Christian Ikenmeyer.
Functional Closure Properties of Finite N-weighted Automata
Cheng Zhang, Arthur Azevedo de Amorim and Marco Gaboardi. Domain Reasoning In TopKAT
Roland Guttenberg. Flattability of Priority Vector Addition Systems
Jakub Rydval, Žaneta Semanišinová and Michał Wrona.
Identifying Tractable Quantified Temporal Constraints within Ord-Horn
Dmitry Chistikov, Alessio Mansutti and Mikhail Starchak.
Integer Linear-Exponential Programming in NP by Quantifier Elimination
Antoine Mottet, Tomáš Nagy and Michael Pinsker.
An order out of nowhere: a new algorithm for infinite-domain CSPs
Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth
Manon Blanc and Olivier Bournez.
The complexity of computing in continuous time: space complexity is precision
Bruno Loff and Mateusz Skomra.
Smoothed analysis of deterministic discounted and mean-payoff games
Wojciech Różowski.
A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions
Michael Benedikt, Chia-Hsuan Lu, Boris Motik and Tony Tan.
Decidability of Graph Neural Networks via Logical Characterizations
Arnaud Carayol and Lucien Charamond. The structure of trees in the pushdown hierarchy
Rohan Acharya, Marcin Jurdziński and Aditya Prakash.
Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
Pavol Kebis, Florian Luca, Joel Ouaknine, Andrew Scoones and James Worrell.
On Transcendence of Numbers Related to Sturmian and Arnoux-Rauzy Words
Jakub Rydval. Homogeneity and Homogenizability: Hard Problems for the Logic SNP
Amina Doumane, Samuel Humeau and Damien Pous.
A finite presentation of treewidth at most 3 graphs
Go Hashimoto, Daniel Gaina and Ionuț Țuțu. Forcing, Transition Algebras, and Calculi
Jakub Gajarský and Rose McCarty.
On classes of bounded tree rank, their interpretations, and efficient sparsification
Yuya Uezato. Regular Expressions with Backreferences and Lookaheads Capture NLOG
Paul Gallot, Sebastian Maneth, Keisuke Nakano and Charles Peyrat.
Deciding Linear Height and Linear Size-to-Height Increase of Macro Tree Transducers
C. Aiswarya, Amaldev Manuel and Saina Sunny. Edit Distance of Finite State Transducers
Christoph Haase, Shankara Naryananan Krishna, Khushraj Madnani, Om Swostik Mishra
and Georg Zetzsche. An efficient quantifier elimination procedure for Presburger arithmetic
Raphael Douglas Giles, Vincent Jackson and Christine Rizkallah.
T-Rex: Termination of Recursive Functions using Lexicographic Linear Combinations
Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer, Corto Mascle, Nicolas Waldburger
and Chana Weil-Kennedy. Verification of Population Protocols with Unordered Data
Quentin Guilmant, Engel Lefaucheux, Joël Ouaknine and James Worell.
The 2-Dimensional Constraint Loop Problem is Decidable
Pascal Baumann, Eren Keskin, Roland Meyer and Georg Zetzsche.
Separability in Büchi Vass and Singly Non-Linear Systems of Inequalities
Mikołaj Bojańczyk, Lê Thành Dũng Nguyên and Rafał Stefański.
Function spaces for orbit-finite sets
More information about the Types-announce
mailing list