ICALP 2023

Session

Track A-2

Jul 11, 2023, 10:30 AM

Seminar Room 4 (HNF)

Conveners

Track A-2: Distributed computing and networks

• Yossi Azar (Session Chair)

Track A-2: Quantum computing

• Thomas Vidick (Session Chair)

Track A-2: Computational geometry

• Laszlo Kozma (Session Chair)

Track A-2: Parameterized complexity

• Debmalya Panigrahi (Session Chair)

Track A-2: Math programming

• Ronald de Wolf (Session Chair)

Track A-2: Online Algorithms

• Petra Berenbrink (Session Chair)

12. Optimal (degree+1)-Coloring in Congested Clique

Sam Coy

7/11/23, 10:30 AM

Sam Coy, Artur Czumaj, Peter Davies and Gopinath Mishra

Abstract: We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u)+1 colors, and the goal is to find a proper coloring using these color palettes. The (Δ+1)-list coloring problem is a natural generalization of the classical (Δ+1)-coloring and...

13. New Additive Emulators

Merav Parter

7/11/23, 10:55 AM

Shimon Kogan and Merav Parter

Abstract: The only known upper bound for this problem is given by an implicit construction of
[Pettie, ICALP 2007] that provides a linear-size emulator with $+\tilde{O}(n^{1/4})$ stretch. No improvement on this problem has been shown since then.

In this work we improve upon the long standing additive stretch of $\tilde{O}(n^{1/4})$, by presenting...

14. Protecting Single-Hop Radio Networks from Message Drops

Dmitry Paramonov

7/11/23, 11:20 AM

Dmitry Paramonov, Gillat Kol, Klim Efremenko and Raghuvansh R. Saxena

Abstract: Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the n participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of...

15. Approximation Algorithms for Network Design in Non-Uniform Fault Models

Rhea Jain

7/11/23, 11:45 AM

Chandra Chekuri and Rhea Jain

Abstract: Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges upto a specific number can fail. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. Our primary interest is in the...

16. Frameworks for Nonclairvoyant Network Design with Deadlines or Delay

Noam Touitou

7/11/23, 12:10 PM

Noam Touitou

Abstract: Clairvoyant network design with deadlines or delay has been studied extensively, culminating in an $O(\log n)$-competitive general framework, where $n$ is the number of possible request types (Azar and Touitou, FOCS 2020). In the nonclairvoyant setting, the problem becomes much harder, as $\mathrm{\Omega }(\sqrt{n})$ lower bounds are known for certain problems (Azar et al.,...

36. #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint

Ben Young

7/11/23, 3:30 PM

Jin-Yi Cai and Ben Young

Abstract: Recently, Mančinska and Roberson proved that two graphs $G$ and $G^{\prime }$ are quantum isomorphic if and only if they admit the same number of homomorphisms from all planar graphs. We extend this result to planar #CSP with any pair of sets $\mathcal{F}$ and ${\mathcal{F}}^{\prime }$ of real-valued, arbitrary-arity constraint functions. Graph homomorphism is the special...

37. Decidability of fully quantum nonlocal games with noisy maximally entangled states

Minglong Qin

7/11/23, 3:55 PM

Minglong Qin and Penghui Yao

Abstract: This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the...

38. Quantum cryptography with classical communication - Parallel remote state preparation for copy-protection, verification, and more

Alexandru Gheorghiu

7/11/23, 4:20 PM

Alexandru Gheorghiu, Tony Metger and Alexander Poremba

Abstract: Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party...

39. Parallel self-testing of EPR pairs under computational assumptions

Honghao Fu

7/11/23, 4:45 PM

Honghao Fu, Daochen Wang and Qi Zhao

Abstract: Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a...

57. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete $k$-Center for Small $k$

Timothy M. Chan

7/12/23, 10:30 AM

Timothy M. Chan, Qizheng He and Yuancheng Yu

Abstract: We study the time complexity of the discrete $k$-center problem and related (exact) geometric set cover problems when $k$ or the size of the cover is small. We obtain a plethora of new results:

• We give the first subquadratic algorithm for \emph{rectilinear discrete 3-center} in 2D, running in $\tilde{O}(n^{3/2})$ time.
• We prove...

58. Rerouting Planar Curves and Disjoint Paths

Takehiro Ito, Yoshio Okamoto, Yusuke Kobayashi, Yuta Nozaki

7/12/23, 10:55 AM

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shunichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki

Abstract: In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$ connecting the same set of terminal pairs, we aim to determine whether $\mathcal{P}$ can be...

59. Approximate Nearest Neighbor for Polygonal Curves under Frechet Distance

Haoqiang Huang

7/12/23, 11:20 AM

Siu-Wing Cheng and Haoqiang Huang

Abstract: We propose $\kappa$-approximate nearest neighbor (ANN) data structures for $n$ polygonal curves with at most $m$ vertices each under the Fr\'{e}chet distance in ${\mathbb{R}}^d$, where $\kappa \in \{1+ϵ,3+ϵ\}$ and $d\ge 2$. We assume that every query curve has at most $k$ vertices, $k\ll m$, and $k$ is given for preprocessing. The...

60. Ortho-radial Drawing in Near-linear Time

Yi-Jun Chang

7/12/23, 11:45 AM

Yi-Jun Chang

Abstract: An orthogonal drawing is an embedding of a plane graph into a grid. In a seminal work of Tamassia (SIAM Journal on Computing, 1987), a simple combinatorial characterization of angle assignments that can be realized as bend-free orthogonal drawings was established, thereby allowing an orthogonal drawing to be combinatorially by listing the angles of all corners. The...

61. The Geometry of Tree-Based Sorting

Magdalen Dobson

7/12/23, 12:10 PM

Magdalen Dobson and Guy Blelloch

Abstract: We study the connections between sorting and the binary search tree (BST) model, with an aim towards showing that the fields are connected more deeply than is currently appreciated. While any BST can be used to sort by inserting the keys one-by-one, this is a very limited relationship and importantly says nothing about parallel sorting. We show...

82. Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar

Jan Jedelský

7/13/23, 10:30 AM

Petr Hlineny and Jan Jedelský

Abstract: Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence) of the given graph down to a single vertex while maintaining limited difference of neighbourhoods of the vertices, and it can be seen as widely generalizing several other...

83. Parameterised and Fine-grained Subgraph Counting, modulo 2

Marc Roth

7/13/23, 10:55 AM

Leslie Ann Goldberg and Marc Roth

Abstract: Given a class of graphs C, the problem ParitySub(C) is defined as follows. The input is a graph H in C together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes C the problem ParitySub(C) is fixed-parameter tractable...

84. Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth

Michał Wlodarczyk

7/13/23, 11:20 AM

Michał Wlodarczyk

Abstract: In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth (tw) of the input graph G. On the one hand, we present an algorithm for Chordal Vertex Deletion with running time 2^O(tw)*|V(G)|, improving upon the running time...

85. Faster parameterized algorithms for modification problems to minor-closed classes

Giannos Stamoulis, Laure Morelle

7/13/23, 11:45 AM

Laure Morelle, Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos

Abstract: Let $\mathcal{G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a {\em $k$-apex} of $\mathcal{G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to $\mathcal{G}$. Our first result is an algorithm that decides whether $G$ is a $k$-apex of ${\cal...

86. Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters

Hans L. Bodlaender

7/13/23, 12:10 PM

Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk

Abstract: We investigate the parameterized complexity of \textsc{Binary CSP} parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows:

• \textsc{Binary CSP} parameterized by the vertex cover number is...

105. Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching

Lichen Zhang

7/13/23, 4:00 PM

Sixue Liu, Zhao Song, Hengjie Zhang, Lichen Zhang and Tianyi Zhou

Abstract: We study the problem of solving linear program in the streaming model. Given a constraint matrix $A\in {\mathbb{R}}^{m\times n}$ and vectors $b\in {\mathbb{R}}^m,c\in {\mathbb{R}}^n$, we develop a space-efficient interior point method that optimizes solely on the dual program. To this end, we obtain efficient algorithms...

106. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability

Tim Seppelt

7/13/23, 4:25 PM

David E. Roberson and Tim Seppelt

Abstract: We show that feasibility of the t-th level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class L_t of graphs such that graphs G and H are not distinguished by the t-th level of the Lasserre hierarchy if and only if they admit...

107. Ellipsoid Fitting Up to a Constant

Jeff Xu, Jun-Ting Hsieh

7/13/23, 4:50 PM

Jun-Ting Hsieh, Pravesh Kothari, Aaron Potechin and Jeff Xu

Abstract: Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in Rd that passes through v_1, v_2, . . . , v_m with high probability when vis are chosen independently from the standard Gaussian distribution N(0, Id). The existence of such an...

123. A General Framework for Learning-Augmented Online Allocation

Debmalya Panigrahi

7/14/23, 10:30 AM

Ilan Cohen and Debmalya Panigrahi

Abstract: Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental problems such as the Santa Claus problem (maximizing minimum utility), Nash welfare maximization...

120. Online Demand Scheduling with Failovers

Rudy Zhou

7/14/23, 10:55 AM

Konstantina Mellou, Marco Molinaro and Rudy Zhou

Abstract: Motivated by cloud computing applications, we study the problem of how to optimally deploy new hardware subject to both power and robustness constraints. To model the situation observed in large-scale data centers, we introduce the \emph{Online Demand Scheduling with Failover} problem. There are $m$ identical devices with capacity...

121. Locality in online, dynamic, sequential, and distributed graph algorithms

Henrik Lievonen, Jukka Suomela

7/14/23, 11:20 AM

Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi and Jukka Suomela

Abstract: In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms.

We introduce a new model of computing, called the online-LOCAL model: the adversary reveals the nodes of the input...

122. Incremental Maximization via Continuization

David Weckbecker

7/14/23, 11:45 AM

Yann Disser, Max Klimm, Kevin Schewior and David Weckbecker

Abstract: We consider the problem of finding an incremental solution to a cardinality-constrained maximization problem that not only captures the solution for a fixed cardinality, but describes how to gradually grow the solution as the cardinality bound increases.
The goal is to find an incremental solution that guarantees a good...

119. Efficient Caching with Reserves via Marking

Sharat Ibrahimpur

7/14/23, 12:10 PM

Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee and Joshua Wang

Abstract: Online caching is among the most fundamental and well-studied problems in the area of online algorithms. Innovative algorithmic ideas and analysis --- including potential functions and primal-dual techniques --- give insight into this still-growing area.
Here, we introduce a novel potential function to...