default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID50th ICALP 2023: Paderborn, Germany
- Kousha Etessami, Uriel Feige, Gabriele Puppis
:
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany. LIPIcs 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2023, ISBN 978-3-95977-278-5 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:38
- Anna R. Karlin:
A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). 1:1-1:1 - Rasmus Kyng:
An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). 2:1-2:1 - Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, Georg Zetzsche:
Context-Bounded Analysis of Concurrent Programs (Invited Talk). 3:1-3:16 - Thomas Vidick:
Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk). 4:1-4:1 - James Worrell:
The Skolem Landscape (Invited Talk). 5:1-5:2 - Anders Aamand, Adam Karczmarz, Jakub Lacki, Nikos Parotsidis, Peter M. R. Rasmussen, Mikkel Thorup:
Optimal Decremental Connectivity in Non-Sparse Graphs. 6:1-6:17 - Peyman Afshani, Pingan Cheng, Aniket Basu Roy, Zhewei Wei:
On Range Summary Queries. 7:1-7:17 - Ishan Agarwal, Richard Cole:
Stable Matching: Choosing Which Proposals to Make. 8:1-8:20 - Daniel Agassy, Dani Dorfman, Haim Kaplan:
Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player. 9:1-9:20 - Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, Jukka Suomela:
Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. 10:1-10:20 - Shyan Akmal, Ce Jin:
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity. 11:1-11:20 - Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey:
Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. 12:1-12:20 - Yossi Azar, Danny Vainstein:
Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering. 13:1-13:18 - Amir Azarmehr, Soheil Behnezhad:
Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation. 14:1-14:15 - Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur:
Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions. 15:1-15:19 - Siddharth Barman, Pooja Kulkarni:
Approximation Algorithms for Envy-Free Cake Division with Connected Pieces. 16:1-16:19 - Paul Beame, Niels Kornerup:
Cumulative Memory Lower Bounds for Randomized and Quantum Computation. 17:1-17:20 - Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser, Malin Rau:
Dynamic Averaging Load Balancing on Arbitrary Graphs. 18:1-18:18 - Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan, László Kozma:
Fast Approximation of Search Trees on Trees with Centroid Trees. 19:1-19:20 - Thiago Bergamaschi:
Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians. 20:1-20:18 - Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco, Archan Ray:
Sublinear Time Eigenvalue Approximation via Random Sampling. 21:1-21:18 - Sudatta Bhattacharya, Michal Koucký:
Streaming k-Edit Approximate Pattern Matching via String Decomposition. 22:1-22:14 - Therese Biedl, Karthik Murali:
On Computing the Vertex Connectivity of 1-Plane Graphs. 23:1-23:16 - Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck:
Fault-Tolerant ST-Diameter Oracles. 24:1-24:20 - Hadley Black, Iden Kalemaj, Sofya Raskhodnikova:
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. 25:1-25:20 - Guy E. Blelloch, Magdalen Dobson:
The Geometry of Tree-Based Sorting. 26:1-26:19 - Hans L. Bodlaender, Carla Groenland, Michal Pilipczuk:
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters. 27:1-27:20 - Andrej Bogdanov, Alon Rosen:
Nondeterministic Interactive Refutations for Nearest Boolean Vector. 28:1-28:14 - Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli:
A 4/3 Approximation for 2-Vertex-Connectivity. 29:1-29:13 - Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir:
Lower Bounds for Pseudo-Deterministic Counting in a Stream. 30:1-30:14 - Manuel Cáceres:
Minimum Chain Cover in Almost Linear Time. 31:1-31:12 - Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans:
Improved Hardness Results for the Guided Local Hamiltonian Problem. 32:1-32:19 - Jin-Yi Cai, Ben Young:
Planar #CSP Equality Corresponds to Quantum Isomorphism - A Holant Viewpoint. 33:1-33:17 - Timothy M. Chan, Qizheng He, Yuancheng Yu:
On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k. 34:1-34:19 - Yi-Jun Chang:
Ortho-Radial Drawing in Near-Linear Time. 35:1-35:20 - Chandra Chekuri, Rhea Jain:
Approximation Algorithms for Network Design in Non-Uniform Fault Models. 36:1-36:20 - Yu Chen, Sanjeev Khanna, Zihan Tan:
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. 37:1-37:16 - Yanlin Chen, Ronald de Wolf:
Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. 38:1-38:21 - Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu:
New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. 39:1-39:20 - Siu-Wing Cheng, Haoqiang Huang:
Approximate Nearest Neighbor for Polygonal Curves Under Fréchet Distance. 40:1-40:18 - Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, Yu Zheng:
Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes. 41:1-41:17 - TsunMing Cheung, Hamed Hatami, Pooya Hatami, Kaave Hosseini:
Online Learning and Disambiguations of Partial Concept Classes. 42:1-42:13 - Ilan Reuven Cohen, Debmalya Panigrahi:
A General Framework for Learning-Augmented Online Allocation. 43:1-43:21 - Omer Cohen Sidon, Dana Ron:
Sample-Based Distance-Approximation for Subsequence-Freeness. 44:1-44:19 - Spencer Compton, Slobodan Mitrovic, Ronitt Rubinfeld:
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling. 45:1-45:16 - Sam Coy, Artur Czumaj, Peter Davies, Gopinath Mishra:
Optimal (Degree+1)-Coloring in Congested Clique. 46:1-46:20 - Yann Disser, Max Klimm, Kevin Schewior, David Weckbecker:
Incremental Maximization via Continuization. 47:1-47:17 - Andrzej Dorobisz, Jakub Kozik:
Local Computation Algorithms for Hypergraph Coloring - Following Beck's Approach. 48:1-48:20 - Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai:
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection via Representative Sets. 49:1-49:16 - Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt, Julian Wargalla:
Connected k-Center and k-Diameter Clustering. 50:1-50:20 - Shaddin Dughmi, Yusuf Hakan Kalayci, Neel Patel:
On Sparsification of Stochastic Packing Problems. 51:1-51:17 - Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova, Adam D. Smith:
Triangle Counting with Local Edge Differential Privacy. 52:1-52:21 - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Protecting Single-Hop Radio Networks from Message Drops. 53:1-53:20 - Charilaos Efthymiou, Weiming Feng:
On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n, d/n). 54:1-54:17 - Charilaos Efthymiou, Kostas Zampetakis:
Broadcasting with Random Matrices. 55:1-55:14 - David Eppstein, Daniel Frishberg:
Improved Mixing for the Convex Polygon Triangulation Flip Walk. 56:1-56:17 - Louis Esperet, Nathaniel Harms, Viktor Zamaraev:
Optimal Adjacency Labels for Subgraphs of Cartesian Products. 57:1-57:11 - Michal Feldman, Federico Fusco, Simon Mauras, Rebecca Reiffenhäuser:
Truthful Matching with Online Items and Offline Agents. 58:1-58:20 - Robert Ferens, Marek Szykula:
Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds. 59:1-59:17 - Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov:
Approximating Long Cycle Above Dirac's Guarantee. 60:1-60:18 - Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos:
Compound Logics for Modification Problems. 61:1-61:21 - Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller:
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs. 62:1-62:13 - Zachary Friggstad, Ramin Mousavi:
An O(log k)-Approximation for Directed Steiner Tree in Planar Graphs. 63:1-63:14 - Honghao Fu, Daochen Wang, Qi Zhao:
Parallel Self-Testing of EPR Pairs Under Computational Assumptions. 64:1-64:19 - Mohit Garg, Felix Hommelsheim, Nicole Megow:
Matching Augmentation via Simultaneous Contractions. 65:1-65:17 - Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Kewen Wu:
On Differentially Private Counting on Trees. 66:1-66:18 - Alexandru Gheorghiu, Tony Metger, Alexander Poremba:
Quantum Cryptography with Classical Communication: Parallel Remote State Preparation for Copy-Protection, Verification, and More. 67:1-67:17 - Leslie Ann Goldberg, Marc Roth:
Parameterised and Fine-Grained Subgraph Counting, Modulo 2. 68:1-68:17 - Gramoz Goranci, Monika Henzinger:
Efficient Data Structures for Incremental Exact and Approximate Maximum Flow. 69:1-69:14 - Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar, Ashish Goel:
Low Sample Complexity Participatory Budgeting. 70:1-70:20 - Daniel Hader, Matthew J. Patitz:
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Cross-Model Simulation in Tile-Based Self-Assembly. 71:1-71:19 - David G. Harris, Vladimir Kolmogorov:
Parameter Estimation for Gibbs Distributions. 72:1-72:21 - Ishay Haviv:
On Finding Constrained Independent Sets in Cycles. 73:1-73:16 - Monika Henzinger, Paul Liu, Jan Vondrák, Da Wei Zheng:
Faster Submodular Maximization for Several Classes of Matroids. 74:1-74:18 - Petr Hlinený, Jan Jedelský:
Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar. 75:1-75:18 - Jakob Bæk Tejs Houen, Mikkel Thorup:
A Sparse Johnson-Lindenstrauss Transform Using Fast Hashing. 76:1-76:20 - Jun-Ting Hsieh, Pravesh K. Kothari:
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. 77:1-77:7 - Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu:
Ellipsoid Fitting up to a Constant. 78:1-78:20 - Dylan Hyatt-Denesik, Afrouz Jabal Ameli, Laura Sanità:
Finding Almost Tight Witness Trees. 79:1-79:16 - Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua R. Wang:
Efficient Caching with Reserves via Marking. 80:1-80:20 - Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki:
Rerouting Planar Curves and Disjoint Paths. 81:1-81:19 - Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto:
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. 82:1-82:17 - Siddharth Iyer, Michael Whitmeyer:
Searching for Regularity in Bounded Functions. 83:1-83:20 - Adam Karczmarz, Piotr Sankowski:
Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs. 84:1-84:20 - Shimon Kogan, Merav Parter:
New Additive Emulators. 85:1-85:17 - Shi Li:
Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems. 86:1-86:20 - Xiantao Li, Chunhao Wang:
Simulating Markovian Open Quantum Systems Using Higher-Order Series Expansion. 87:1-87:20 - S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, Tianyi Zhou:
Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching. 88:1-88:14 - Shu Liu, Chaoping Xing, Chen Yuan:
List Decoding of Rank-Metric Codes with Row-To-Column Ratio Bigger Than 1/2. 89:1-89:14 - Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan:
Breaking the All Subsets Barrier for Min k-Cut. 90:1-90:19 - Claire Mathieu, Hang Zhou:
A Tight (1.5+ε)-Approximation for Unsplittable Capacitated Vehicle Routing on Trees. 91:1-91:16 - Konstantina Mellou, Marco Molinaro, Rudy Zhou:
Online Demand Scheduling with Failovers. 92:1-92:20 - Laure Morelle, Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos:
Faster Parameterized Algorithms for Modification Problems to Minor-Closed Classes. 93:1-93:19 - Kazusato Oko, Shinsaku Sakaue, Shin-ichi Tanigawa:
Nearly Tight Spectral Sparsification of Directed Hypergraphs. 94:1-94:19 - Rotem Oshman, Tal Roth:
The Communication Complexity of Set Intersection Under Product Distributions. 95:1-95:20 - Pan Peng, Yuyang Wang:
An Optimal Separation Between Two Property Testing Models for Bounded Degree Directed Graphs. 96:1-96:16 - Minglong Qin, Penghui Yao:
Decidability of Fully Quantum Nonlocal Games with Noisy Maximally Entangled States. 97:1-97:20 - Rajmohan Rajaraman, David Stalfa, Sheng Yang:
Scheduling Under Non-Uniform Job and Machine Delays. 98:1-98:20 - Nicolas Resch, Chen Yuan, Yihan Zhang:
Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery. 99:1-99:18 - Eric Rivals, Michelle Sweering, Pengfei Wang:
Convergence of the Number of Period Sets in Strings. 100:1-100:14 - David E. Roberson, Tim Seppelt:
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability. 101:1-101:18 - Ittai Rubinstein:
Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem. 102:1-102:20 - Thomas Sauerwald, He Sun, Danny Vagnozzi:
The Support of Open Versus Closed Random Walks. 103:1-103:21 - Tatsuya Terao:
Faster Matroid Partition Algorithms. 104:1-104:20 - Noam Touitou:
Frameworks for Nonclairvoyant Network Design with Deadlines or Delay. 105:1-105:20 - Michal Wlodarczyk:
Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth. 106:1-106:20 - Or Zamir:
The Wrong Direction of Jensen's Inequality Is Algorithmically Right. 107:1-107:10 - Ruizhe Zhang, Xinzhi Zhang:
A Hyperbolic Extension of Kadison-Singer Type Results. 108:1-108:14 - Bader Abu Radi, Orna Kupferman:
On Semantically-Deterministic Automata. 109:1-109:20 - Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, Georg Zetzsche:
Checking Refinement of Asynchronous Programs Against Context-Free Specifications. 110:1-110:20 - Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann:
On the Limits of Decision: the Adjacent Fragment of First-Order Logic. 111:1-111:21 - Michael Benedikt, Dmitry Chistikov, Alessio Mansutti:
The Complexity of Presburger Arithmetic with Power or Powers. 112:1-112:18 - Christoph Berkholz, Harry Vinall-Smeeth:
A Dichotomy for Succinct Representations of Homomorphisms. 113:1-113:19 - Fabian Birkmann, Stefan Milius, Henning Urbat:
Nominal Topology for Data Languages. 114:1-114:21 - Michael Blondin, François Ladouceur:
Population Protocols with Unordered Data. 115:1-115:20 - Manuel Bodirsky, Simon Knäuer:
Network Satisfaction Problems Solved by k-Consistency. 116:1-116:20 - Mikolaj Bojanczyk, Lê Thành Dung Nguyên:
Algebraic Recognition of Regular Functions. 117:1-117:19 - Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, Pierre Vandenhove:
How to Play Optimally for Regular Objectives? 118:1-118:18 - Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, Aris Papadopoulos:
Monadic NIP in Monotone Classes of Relational Structures. 119:1-119:18 - Titouan Carette, Etienne Moutot, Thomas Perez, Renaud Vilmart:
Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus. 120:1-120:17 - Olivier Carton, Gaëtan Douéneau-Tabot, Emmanuel Filiot, Sarah Winter:
Deterministic Regular Functions of Infinite Words. 121:1-121:18 - Antonio Casares, Pierre Ohlmann:
Characterising Memory in Infinite Games. 122:1-122:18 - Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel:
Approximate Model Counting: Is SAT Oracle More Powerful Than NP Oracle? 123:1-123:17 - Ruiwen Dong:
The Identity Problem in ℤ ≀ ℤ Is Decidable. 124:1-124:20 - Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk:
Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes. 125:1-125:18 - Javier Esparza, Vincent P. Grande:
Black-Box Testing Liveness Properties of Partially Observable Stochastic Systems. 126:1-126:17 - Austen Z. Fan, Paraschos Koutris, Hangdong Zhao:
The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems. 127:1-127:20 - Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk:
Flipper Games for Monadically Stable Graph Classes. 128:1-128:16 - Thomas A. Henzinger, Pavol Kebis, Nicolas Mazzocchi, N. Ege Saraç:
Regular Methods for Operator Precedence Languages. 129:1-129:20 - George Kenison, Joris Nieuwveld, Joël Ouaknine, James Worrell:
Positivity Problems for Reversible Linear Recurrence Sequences. 130:1-130:17 - Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks, Karol Wegrzycki:
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality. 131:1-131:20 - Michael Lampis:
First Order Logic on Pathwidth Revisited Again. 132:1-132:17 - Moritz Lichter:
Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting. 133:1-133:20 - Markus Lohrey, Andreas Rosowski:
On the Complexity of Diameter and Related Problems in Permutation Groups. 134:1-134:18 - Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk:
Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes. 135:1-135:17 - Wojciech Rozowski, Tobias Kappé, Dexter Kozen, Todd Schmid, Alexandra Silva:
Probabilistic Guarded KAT Modulo Bisimilarity: Completeness and Complexity. 136:1-136:20 - Frits W. Vaandrager, Thorsten Wißmann:
Action Codes. 137:1-137:20
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-15 19:44 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
