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)
Presentation materials
Andrej Bogdanov and Alon Rosen
Abstract: Most
Certifying NBV instances is relevant to the...
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...
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...
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...
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...
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
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)