Asaf Petruschka

SODA Conference 2025 Conference Paper

Parks and Recreation: Color Fault-Tolerant Spanners Made Local

• Merav Parter
• Asaf Petruschka
• Shay Sapir
• Elad Tzalik

STOC Conference 2024 Conference Paper

Connectivity Labeling and Routing with Multiple Vertex Failures

• Merav Parter
• Asaf Petruschka
• Seth Pettie

We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f -vertex/edge fault tolerant ( f -V/EFT) connectivity labeling is a scheme that produces succinct labels for the vertices (and possibly to the edges) of an n -vertex graph G , such that given only the labels of two vertices s , t and of at most f faulty vertices/edges F , one can infer if s and t are connected in G − F . The primary complexity measure is the maximum label length (in bits). The f -EFT setting is relatively well understood: [Dory and Parter, PODC 2021] gave a randomized scheme with succinct labels of O (log 3 n ) bits, which was subsequently derandomized by [Izumi et al., PODC 2023] with Õ( f 2 )-bit labels. As both noted, handling vertex faults is more challenging. The known bounds for the f -VFT setting are far away: [Parter and Petruschka, DISC 2022] gave Õ( n 1−1/2 Θ( f ) )-bit labels, which is linear in n already for f =Ω(loglog n ). In this work we present an efficient f -VFT connectivity labeling scheme using poly ( f , log n ) bits. Specifically, we present a randomized scheme with O ( f 3 log 5 n )-bit labels, and a derandomized version with O ( f 7 log 13 n )-bit labels, compared to an Ω( f )-bit lower bound on the required label length. Our schemes are based on a new low-degree graph decomposition that improves on [Duan and Pettie, SODA 2017], and facilitates its distributed representation into labels. This is accompanied with specialized linear graph sketches that extend the techniques of the Dory and Parter to the vertex fault setting, which are derandomized by adapting the approach of Izumi et al. and combining it with hit-miss hash families of [Karthik and Parter, SODA 2021]. Finally, we show that our labels naturally yield routing schemes avoiding a given set of at most f vertex failures with table and header sizes of only poly ( f ,log n ) bits. This improves significantly over the linear size bounds implied by the EFT routing scheme of Dory and Parter.

TCS Journal 2023 Journal Article

Lazy regular sensing

• Orna Kupferman
• Asaf Petruschka

A complexity measure for regular languages based on the sensing required to recognize them was recently introduced by Almagor, Kuperberg, and Kupferman. Intuitively, the sensing cost quantifies the detail in which a random input word has to be read in order to decide its membership in the language, when the input letters composing the word are truth assignments to a finite set of signals. We introduce the notion of lazy sensing, where the signals are not sensed simultaneously. Rather, the signals are ordered, and a signal is sensed only if the values of the signals sensed so far have not determined the successor state. We study four classes of lazy sensing, induced by distinguishing between the cases where the order of the signals is static or dynamic (that is, fixed in advance or depends on the values of the signals sensed so far), and the cases where the order is global or local (that is, the same for all states of the automaton, or not). We examine the different classes of lazy sensing and the saving they enable, with respect to each other and with respect to (non-lazy) sensing. We also examine the trade offs between sensing cost and size. Our results show that the good properties of sensing are preserved in the lazy setting. In particular, saving sensing does not conflict with saving size: in all four classes, the lazy-sensing cost of a regular language can be attained in the minimal automaton recognizing the language.