ICALP 2023

Session

Track A-3

Jul 11, 2023, 10:30 AM

Seminar Room 5 (HNF)

Conveners

Track A-3: Probabilistic analysis

• Vladimir Kolmogorov (Session Chair)

Track A-3: Data structures

• Merav Parter (Session Chair)

Track A-3: Random walks and related topics

• Andrej Bogdanov (Session Chair)

Track A-3: Approximation Algorithms

• Sharat Ibrahimpur (Session Chair)

Track A-3: Property Testing

• Talya Eden (Session Chair)

Track A-3: Coding and Privacy

• C.S. Karthik (Session Chair)

17. Nondeterministic Refutations for Nearest Boolean Vector

Andrej Bogdanov

7/11/23, 10:30 AM

Andrej Bogdanov and Alon Rosen

Abstract: Most $n$-dimensional subspaces $\mathcal{A}$ of $\mathbb{R}^m$ are $\Omega(\sqrt{m})$-far from the Boolean cube $\{-1,1\}^m$ when $n < cm$ for some constant $c > 0$. How hard is it to certify that the Nearest Boolean Vector (NBV) is at least $\gamma \sqrt{m}$ far from a given random $\mathcal{A}$?

Certifying NBV instances is relevant to the...

18. Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem

Ittai Rubinstein

7/11/23, 10:55 AM

Ittai Rubinstein

Abstract: The {\em insertion-deletion channel} takes as input a binary string $x \in\{0, 1\}^n$, and outputs a string $\widetilde{x}$ where some of the bits have been deleted and others inserted independently at random.
In the {\em trace reconstruction problem}, one is given many outputs (called {\em traces}) of the insertion-deletion channel applied to the same input...

19. Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs

Andreas Göbel, Leon Schiller

7/11/23, 11:20 AM

Tobias Friedrich, Andreas Göbel, Maximilian Katzmann and Leon Schiller

Abstract: A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of...

20. On Sparsification of Stochastic Packing Problems

Yusuf Hakan Kalaycı

7/11/23, 11:45 AM

Shaddin Dughmi, Yusuf Hakan Kalaycı and Neel Patel

Abstract: Motivated by recent progress on stochastic matching with few queries, we embark on a systematic study of the sparsification of stochastic packing problems more generally. Specifically, we consider packing problems where elements are independently active with a given probability $p$, and ask whether one can (non-adaptively) compute...

21. The wrong direction of Jensen’s inequality is algorithmically right

Or Zamir

7/11/23, 12:10 PM

Or Zamir

Abstract: Let $\mathcal{A}$ be an algorithm with expected running time $e^X$, conditioned on the value of some random variable $X$.
We construct an algorithm $\mathcal{A'}$ with expected running time $O\left(e^{E[X]}\right)$, that fully executes $\mathcal{A}$.
In particular, an algorithm whose running time is a random variable $T$ can be converted to one with expected running...

40. On Range Summary Queries

Pingan Cheng

7/11/23, 3:30 PM

Peyman Afshani, Pingan Cheng, Aniket Basu Roy and Zhewei Wei

Abstract: We study the query version of the heavy hitter and approximate quantile problems.
In the former problem, the input is a parameter $\varepsilon$, and a set $P$ of $n$ points in $R^d$
where each point is assigned a color from a set $C$ and the goal is to
build a structure such that given any geometric range...

41. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Gramoz Goranci

7/11/23, 3:55 PM

Gramoz Goranci and Monika Henzinger

Abstract: We show an $(1+\epsilon)$-approximation algorithm for maintaining maximum $s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)} \epsilon^{-1/2}$ amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation...

42. Fault-Tolerant ST-Diameter Oracles

Davide Bilò

7/11/23, 4:20 PM

Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann and Martin Schirneck

Abstract: We study the problem of estimating the $ST$-diameter of a graph that is subject to a bounded number of edge failures. An \emph{$f$-edge fault-tolerant $ST$-diameter oracle} ($f$-FDO-$ST$) is a data structure that preprocesses a given graph $G$, two sets of vertices $S,T$, and positive...

43. Optimal Adjacency Labels for Subgraphs of Cartesian Products

Nathaniel Harms, Viktor Zamaraev

7/11/23, 4:45 PM

Louis Esperet, Nathaniel Harms and Viktor Zamaraev

Abstract: For any hereditary graph class F, we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in F. As a consequence, we show that, if F admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic...

62. Parameter estimation for Gibbs distributions

Vladimir Kolmogorov

7/12/23, 10:30 AM

David Harris and Vladimir Kolmogorov

Abstract: A central problem in computational statistics is to convert a procedure for \emph{sampling} combinatorial objects into a procedure for \emph{counting} those objects, and vice versa. We will consider sampling problems which come from \emph{Gibbs distributions}, which are families of probability distributions over a discrete space $\Omega$ with...

63. On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n)

Weiming Feng

7/12/23, 10:55 AM

Charilaos Efthymiou and Weiming Feng

Abstract: We study the single-site Glauber dynamics for the fugacity \lambda, Hard-core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n,d/n) and for fugacity \lambda < \frac{d^d}{(d-1)^{d+1}}, the mixing time of Glauber dynamics is n^{1 + O(1/\log \log n)}.

Our result improves on the recent elegant...

64. Broadcasting with Random Matrices

Konstantinos Zampetakis

7/12/23, 11:20 AM

Konstantinos Zampetakis and Charilaos Efthymiou

Abstract: Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem for the related distributions on the tree, and on the sparse random graph G(n,d/n).

Both cases, reduce naturally to studying broadcasting models on the tree, where each edge has its own broadcasting matrix and this matrix is drawn...

65. Improved mixing for the convex polygon triangulation flip walk

Daniel Frishberg

7/12/23, 11:45 AM

David Eppstein and Daniel Frishberg

Abstract: We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n^3 log^3 n), the first progress since McShine and Tetali's O(n^5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Omega(1/(sqrt n log n)) and O(1/sqrt n)---asymptotically tight up to an O(log n) factor---for the...

66. The Support of Open versus Closed Random Walks

He Sun

7/12/23, 12:10 PM

Thomas Sauerwald, He Sun and Danny Vagnozzi

Abstract: A closed random walk of length $\ell$ on an undirected and connected graph G=(V,E) is a random walk that returns to the start vertex at step $\ell$, and its properties have been very recently related to problems in different mathematical fields, e.g., geometry and combinatorics (Jiang et al., Annals of Mathematics '21) and spectral graph...

87. Connected k-Center and k-Diameter Clustering

Kelin Luo

7/13/23, 10:30 AM

Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt and Julian Wargalla

Abstract: Motivated by an application from geodesy, we study the connected k-center problem and the connected k-diameter problem. These problems arise from the classical k-center and k-diameter problems by adding a side constraint. For the side constraint, we are given an undirected connectivity graph G on...

88. Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering

Danny Vainstein, Yossi Azar

7/13/23, 10:55 AM

Yossi Azar and Danny Vainstein

Abstract: We present a novel technique to cluster points in a metric space. A well-known non-parametric objective is to embed the metric space into a simpler structured metric space such as a line (i.e., Linear Arrangement) or a binary tree (i.e., Hierarchical Clustering). Points which are close in the metric space should be mapped to close points/leaves in...

89. Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm

Jun-Ting Hsieh

7/13/23, 11:20 AM

Jun-Ting Hsieh and Pravesh Kothari

Abstract: In this note, we describe a $\alpha_{GW} + \tilde{\Omega}(1/d^2)$-factor approximation algorithm for Max-Cut on weighted graphs of degree at most $d$. Here, $\alpha_{GW} \approx 0.878$ is the worst-case approximation ratio of the Goemans-Williamson rounding for Max-Cut. This improves on previous results for unweighted graphs by Feige, Karpinski,...

90. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection

Ilan Doron

7/13/23, 11:45 AM

Ilan Doron, Ariel Kulik and Hadas Shachnai

Abstract: We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al. (Math. Programming, 2011), Chekuri, Vondrak and Zenklusen (SODA 2011)], it has been an intriguing open question whether these problems admit a fully PTAS...

91. Scheduling under Non-Uniform Job and Machine Delays

David Stalfa

7/13/23, 12:10 PM

David Stalfa, Rajmohan Rajaraman and Sheng Yang

Abstract: We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given a set of $n$ unit size precedence-ordered jobs, and a set of $m$ related machines each with size $m_i$ (machine $i$ can execute at most $m_i$ jobs at any time). Each...

108. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Hadley Black, Iden Kalemaj

7/13/23, 4:00 PM

Hadley Black, Iden Kalemaj and Sofya Raskhodnikova

Abstract: We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra~(SICOMP 2018) for Boolean functions to the case of real-valued functions $f:\{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an...

109. An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs

Pan Peng

7/13/23, 4:25 PM

Pan Peng and Yuyang Wang

Abstract: We revisit the relation between two fundamental property testing models for bounded-degree \emph{directed} graphs: the \emph{bidirectional} model in which the algorithms are allowed to query both the outgoing edges and incoming edges of a vertex, and the \emph{unidirectional} model in which only queries to the outgoing edges are allowed. Czumaj, Peng and...

110. Sample-based distance-approximation for subsequence-freeness

Omer Cohen Sidon

7/13/23, 4:50 PM

Dana Ron and Omer Cohen Sidon

Abstract: In this work, we study the problem of approximating the distance to subsequence-freeness in the sample-based distribution-free model. For a given subsequence (word) $w = w_1 \dots w_k$, a sequence (text) $T = t_1 \dots t_n$ is said to contain $w$ if there exist indices $1 \leq i_1 < \dots < i_k \leq n$ such that $t_{i_{j}} = w_j$ for every $1 \leq j...

124. Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery

Yihan Zhang

7/14/23, 10:30 AM

Nicolas Resch, Chen Yuan and Yihan Zhang

Abstract: In this work we consider the list-decodability and list-recoverability of arbitrary $q$-ary codes, for all integer values of $q\geq 2$. A code is called $(p,L)_q$-list-decodable if every radius $pn$ Hamming ball contains less than $L$ codewords; $(p,\ell,L)_q$-list-recoverability is a generalization where we place radius $pn$ Hamming balls...

125. Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes

Kuan Cheng

7/14/23, 10:55 AM

Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei and Yu Zheng

Abstract: This work continues the study of linear error correcting codes against adversarial insertion deletion errors (insdel errors). Previously, the work of Cheng, Guruswami, Haeupler, and Li \cite{CGHL21} showed the existence of asymptotically good linear insdel codes that can correct arbitrarily close to $1$ fraction of errors...

126. List Decoding of Rank-Metric Codes with Row-to-Column Ratio Bigger Than 1/2

Chaoping Xing

7/14/23, 11:20 AM

Shu Liu, Chaoping Xing and Chen Yuan

Abstract: Despite of numerous results about the list decoding of Hamming-metric codes, development of list decoding on rank-metric codes is not rapid as its counterpart. The limit on list decoding obeys the Gilbert-Varshamov bound in both the metrics. In the case of the Hamming-metric, the Gilbert-Varshamov bound is a trade-off among rate, decoding...

127. On Differentially Private Counting on Trees

Pasin Manurangsi

7/14/23, 11:45 AM

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi and Kewen Wu

Abstract: We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a new error measure for this problem by considering a combination of multiplicative and additive approximation to the query results.
We...

128. Triangle Counting with Local Edge Differential Privacy

Talya Eden

7/14/23, 12:10 PM

Talya Eden, Sofya Raskhodnikova, Quanquan C. Liu and Adam Smith

Abstract: Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study triangle counting in the
noninteractive and interactive local model with edge differential privacy (that, intuitively, requires that
the...