2 citations · 4 across the 4 of their papers we have counts for
7 papers
On Mappings on the Hypercube with Small Average Stretch
Lucas Boczkowski, Igor Shinkar
Let be a set of size , and let be a bijection. We define the average stretch of as ${\sf avgStretch}(ϕ) = {\mathb…
Limits for Rumor Spreading in stochastic populations
Lucas Boczkowski, Ofer Feinerman, Amos Korman +1
Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate…
Searching Trees with Permanently Noisy Advice: Walking and Query Algorithms
Lucas Boczkowski, Uriel Feige, Amos Korman +1
We consider a search problem on trees in which the goal is to find an adversarially placed treasure, while relying on local, partial information. Specifically, each node in the tre…
Streaming Communication Protocols
Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez
We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that…
Sensitivity of mixing times in Eulerian digraphs
Lucas Boczkowski, Yuval Peres, Perla Sousi
Let be a lazy random walk on a graph . If is undirected, then the mixing time is upper bounded by the maximum hitting time of the graph. This fails for directed chains,…
Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
Lucas Boczkowski, Amos Korman, Emanuele Natale
This paper considers the basic model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify…
Extended Extremes of Information Combining
Lucas Boczkowski
Extremes of information combining inequalities play an important role in the analysis of sparse-graph codes under message-passing decoding. We introduce new tools for the derivatio…