Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Bringmann, Karl ; Grohe, Martin ; Puppis, Gabriele ; Svensson, Ola (Ed.)We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)approximation in Õ(n^ω/t^{ω2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)approximation algorithms for the number of hcycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h2)},n)), the time to multiply n × n/(t^{1/(h2)}) by n/(t^{1/(h2)) × n matrices. Finally, we show that under popular finegrained hypotheses, this running time is optimal.more » « lessFree, publiclyaccessible full text available January 1, 2025

The radio network model is a wellstudied model of wireless, multihop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random. In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a nonadaptive protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of poly(log Delta, log log n) rounds where n is the number nodes in the network and Delta is the max degree. Moreover, we demonstrate that, even if the simulated protocol is not nonadaptive, it can be simulated with a multiplicative O(Delta log^2 Delta) cost in the number of rounds. Lastly, we argue that simulations with a multiplicative overhead of o(log Delta) are unlikely to exist by proving that an Omega(log Delta) multiplicative round overhead is necessary under certain natural assumptions.more » « less

The widelystudied radio network model [Chlamtac and Kutten, 1985] is a graphbased description that captures the inherent impact of collisions in wireless communication. In this model, the strong assumption is made that node v receives a message from a neighbor if and only if exactly one of its neighbors broadcasts. We relax this assumption by introducing a new noisy radio network model in which random faults occur at senders or receivers. Specifically, for a constant noise parameter p ∈ [0,1), either every sender has probability p of transmitting noise or every receiver of a single transmission in its neighborhood has probability p of receiving noise. We first study singlemessage broadcast algorithms in noisy radio networks and show that the Decay algorithm [BarYehuda et al., 1992] remains robust in the noisy model while the diameterlinear algorithm of Gasieniec et al., 2007 does not. We give a modified version of the algorithm of Gasieniec et al., 2007 that is robust to sender and receiver faults, and extend both this modified algorithm and the Decay algorithm to robust multimessage broadcast algorithms, broadcasting Ω(1/log n log log n) and Ω(1/log n) messages per round, respectively. We next investigate the extent to which (network) coding improves throughput in noisy radio networks. In particular, we study the coding cap  the ratio of the throughput of coding to that of routing  in noisy radio networks. We address the previously perplexing result of Alon et al. 2014 that worst case coding throughput is no better than worst case routing throughput up to constants: we show that the worst case throughput performance of coding is, in fact, superior to that of routing  by a Θ(log(n)) gap  provided receiver faults are introduced. However, we show that sender faults have little effect on throughput. In particular, we show that any coding or routing scheme for the noiseless setting can be transformed to be robust to sender faults with only a constant throughput overhead. These transformations imply that the results of Alon et al., 2014 carry over to noisy radio networks with sender faults as well. As a result, if sender faults are introduced then there exist topologies for which there is a Θ(log log n) gap, but the worst case throughput across all topologies is Θ(1/log n) for both coding and routing.more » « less