ICALP 2023

Session

Track A-4

Jul 11, 2023, 10:30 AM

F0.530 (HNI)

Conveners

Track A-4: Mixed topics

• Pasin Manurangsi (Session Chair)

Track A-4: Sublinear algorithms, streaming

• Yusuke Kobayashi (Session Chair)

Track A-4: Computational and communication complexity, and hardness

• Michal Koucky (Session Chair)

Track A-4: Graphs, hypergraphs and strings

• Aaron Bernstein (Session Chair)

22. Searching for Regularity in Bounded Functions

Michael Whitmeyer

7/11/23, 10:30 AM

Michael Whitmeyer and Siddharth Iyer

Abstract: Given a bounded function $f$ on $\mathbb F_2^n$, this work seeks a large affine subspace $\mathcal U$ such that $f$, when restricted to $\cal U$, has small nontrivial Fourier coefficients.
It is not hard to see that a random function is such that all its Fourier coefficients are extremely small already, so we focus on a natural class...

23. A Sparse Johnson-Lindenstrauss Transform using Fast Hashing

Jakob Bæk Tejs Houen

7/11/23, 10:55 AM

Jakob Bæk Tejs Houen and Mikkel Thorup

Abstract: The \emph{Sparse Johnson-Lindenstrauss Transform} of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map $A \in R^{m \times u}$ in $\ell_2$ that preserves distances up to distortion of $1 + \varepsilon$ with probability $1 - \delta$, where $m = O(\varepsilon^{-2} \log 1/\delta)$ and each column of $A$ has $O(\varepsilon...

24. A Hyperbolic Extension of Kadison-Singer Type Results

Xinzhi Zhang

7/11/23, 11:20 AM

Ruizhe Zhang and Xinzhi Zhang

Abstract: In 2013, Marcus, Spielman, and Srivastava resolved the famous Kadison-Singer conjecture. It states that for $n$ independent random vectors $v_1,\cdots, v_n$ that have expected squared norm bounded by $\epsilon$ and are in the isotropic position in expectation, there is a positive probability that the determinant polynomial $\det(xI - \sum_{i=1}^n...

25. The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Cross-Model Simulation in Tile-Based Self-Assembly

Daniel Hader

7/11/23, 11:45 AM

Daniel Hader and Matthew Patitz

Abstract: Algorithmic self-assembly occurs when components in a disorganized collection autonomously combine to form structures and, by their design and the dynamics of the system, are forced to intrinsically follow the execution of algorithms. Motivated by applications in DNA-nanotechnology, theoretical investigations in algorithmic tile-based self-assembly...

26. Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds

Marek Szykuła

7/11/23, 12:10 PM

Robert Ferens and Marek Szykuła

Abstract: A complete deterministic finite (semi)automaton (DFA) with a set of states $Q$ is \emph{completely reachable} if every non-empty subset of $Q$ can be obtained as the image of the action of some word applied to $Q$.
The concept of completely reachable automata appeared several times, in particular, in connection with synchronizing automata; the...

44. Lower Bounds for Pseudo-Deterministic Counting in a Stream

Shay Sapir

7/11/23, 3:30 PM

Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan and Shay Sapir

Abstract: Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many streaming problems, both relaxations must be employed simultaneously, to avoid an exponentially larger (and often trivial) space...

45. Streaming $k$-edit approximate pattern matching via string decomposition

Michal Koucky

7/11/23, 3:55 PM

Sudatta Bhattacharya and Michal Koucky

Abstract: In this paper we give an algorithm for streaming $k$-edit approximate pattern matching which uses space $\widetilde{O}(k^2)$ and time $\widetilde{O}(k^3)$ per arriving symbol. This improves substantially on the recent algorithm of Kociumaka, Porat and Starikovskaya (2021) which uses space $\widetilde{O}(k^5)$ and time $\widetilde{O}(k^8)$ per...

46. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics

Yu Chen

7/11/23, 4:20 PM

Sanjeev Khanna, Yu Chen and Zihan Tan

Abstract: We consider the design of sublinear space and query complexity algorithms for estimating the cost of a minimum spanning tree (MST) and the cost of a minimum traveling salesman (TSP) tour in a metric on $n$ points. We start by exploring this estimation task in the regime of $o(n)$ space, when the input is presented as a stream of all $n \choose...

47. Sublinear Time Eigenvalue Approximation via Random Sampling

Archan Ray

7/11/23, 4:45 PM

Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco and Archan Ray

Abstract: We study the problem of approximating the eigenspectrum of a symmetric matrix $\mathbf A \in \mathbb{R}^{n \times n}$ with bounded entries (i.e., $\|\mathbf A\|_{\infty} \leq 1$). We present a simple sublinear time algorithm that approximates all eigenvalues of $\mathbf{A}$ up to additive error...

67. Low-depth arithmetic circuit lower bounds: Bypassing set-multilinearization

Bhargav Thankey, Prashanth Amireddy

7/12/23, 10:30 AM

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha and Bhargav Thankey

Abstract: A recent breakthrough work of Limaye, Srinivasan, and Tavenas [FOCS 2021] proved superpolynomial lower bounds for low-depth arithmetic circuits via a “hardness escalation" approach: they proved lower bounds for low-depth set-multilinear circuits and then lifted the bounds to low-depth general circuits....

68. New PRGs for Unbounded-width/Adaptive-order Read-once Branching Programs

Hongxun Wu

7/12/23, 10:55 AM

Lijie Chen, Xin Lyu, Avishay Tal and Hongxun Wu

Abstract: We give the first pseudorandom generators with sub-linear seed length for the following variants of read-once branching programs (roBPs):

1. First, we show there is an explicit PRG of seed length O(log^2(n/eps) log(n)) that fools unbounded-width unordered permutation branching programs with a single accept state, where $n$ is the...

69. The Communication Complexity of Set Intersection under Product Distributions

Tal Roth

7/12/23, 11:20 AM

Rotem Oshman and Tal Roth

Abstract: We consider a multiparty setting where $k$ parties have private inputs $X_1,\ldots,X_k \subseteq [n]$ and wish to compute the intersection $\bigcap_{\ell=1}^k X_{\ell}$ of their sets, using as little communication as possible. This task generalizes the well-known problem of set disjointness, where the parties are required only to determine whether the...

70. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation

Amir Azarmehr

7/12/23, 11:45 AM

Amir Azarmehr and Soheil Behnezhad

Abstract: We study the robust communication complexity of maximum matching. Edges of an arbitrary
n-vertex graph G are randomly partitioned between Alice and Bob independently and uniformly.
Alice has to send a single message to Bob such that Bob can find an (approximate) maximum
matching of the whole graph G. We specifically study the best...

71. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Takehiro Ito, Yoshio Okamoto, Yusuke Kobayashi, Yuta Nozaki

7/12/23, 12:10 PM

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki and Yoshio Okamoto

Abstract: We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known...

92. Local Computation Algorithms for Hypergraph Coloring - following Beck's approach

Andrzej Dorobisz

7/13/23, 10:30 AM

Andrzej Dorobisz and Jakub Kozik

Abstract: We investigate local computation algorithms (LCA) for two-coloring of k-uniform hypergraphs. We focus on hypergraph instances that satisfy strengthened assumption of the Lovasz Local Lemma of the form 2^{1−αk}(Δ+1)e<1, where Δ is the bound on the maximum edge degree. The main question which arises here is for how large α there exists a LCA that is...

93. Nearly Tight Spectral Sparsification of Directed Hypergraphs

Kazusato Oko

7/13/23, 10:55 AM

Kazusato Oko, Shinsaku Sakaue and Shin-ichi Tanigawa

Abstract: Spectral hypergraph sparsification, an attempt to extend well-known spectral graph sparsification to hypergraphs, has been extensively studied over the past few years. For undirected hypergraphs, Kapralov, Krauthgamer, Tardos, and Yoshida~(2022) have proved an $\varepsilon$-spectral sparsifier of the optimal $O^*(n)$ size, where...

94. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

Dani Dorfman

7/13/23, 11:20 AM

Daniel Agassy, Dani Dorfman and Haim Kaplan

Abstract: A $(\phi,\epsilon)$-expander-decomposition of a graph $G$ (with $n$ vertices and $m$ edges) is a partition of $V$ into clusters $V_1,\ldots,V_k$ with conductance $\Phi(G[V_i]) \ge \phi$, such that there are at most $\epsilon m$ inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. We give a randomized...

95. On Finding Constrained Independent Sets in Cycles

Ishay Haviv

7/13/23, 11:45 AM

Ishay Haviv

Abstract: A subset of $[n] = \{1,2,\ldots,n\}$ is called stable if it forms an independent set in the cycle on the vertex set $[n]$. In 1978, Schrijver proved via a topological argument that for all integers $n$ and $k$ with $n \geq 2k$, the family of stable $k$-subsets of $[n]$ cannot be covered by $n-2k+1$ intersecting families. We study two total search problems whose...

96. Convergence of the number of period sets in strings

Eric Rivals, Pengfei Wang

7/13/23, 12:10 PM

Eric Rivals, Michelle Sweering and Pengfei Wang

Abstract: Consider words of length n. The set of all periods of a word of length $n$ is a subset of {0,1,2,...,n-1}. However, any subset of {0,1,2,...,n-1} is not necessarily a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko have proposed to encode the set of periods of a word into an n long binary string, called an...