Distributed Testing of Excluded Subgraphs

Teoria statistica delle classi e calcolo delle probabilità

C.E. Bonferroni · 1936

Earlier work this paper cites.

On sets of integers which contain no three terms in arithmetical progression

Felix A Behrend · 1946

Earlier work this paper cites.

Property testing and its connection to learning and approximation

Oded Goldreich, Shari Goldwasser, and Dana Ron · 1998

Earlier work this paper cites.

Distributed Computing: A Locality-sensitive Approach

David Peleg · 2000

Earlier work this paper cites.

MST construction in 𝒪 ⁡ ( log ⁡ log ⁡ n ) {{\mathcal{O}}}(\log\log n) communication rounds

Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg · 2003

Earlier work this paper cites.

Probability and Computing: Randomized Algorithms and Probabilistic Analysis

M. Mitzenmacher and E. Upfal · 2005

Earlier work this paper cites.

An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem

Michael Elkin · 2006

Earlier work this paper cites.

Distributed MST for constant diameter graphs

Zvi Lotker, Boaz Patt-Shamir, and David Peleg · 2006

Earlier work this paper cites.

Testing triangle-freeness in general graphs

Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron · 2008

Earlier work this paper cites.

Property Testing - Current Research and Surveys

Oded Goldreich, editor · 2010

Earlier work this paper cites.

Local distributed decision

Pierre Fraigniaud, Amos Korman, and David Peleg · 2011

Cited alongside, same era.

Locally checkable proofs

Mika Göös and Jukka Suomela: · 2011

Cited alongside, same era.

The round complexity of distributed sorting

Boaz Patt-Shamir and Marat Teplitsky · 2011

Cited alongside, same era.

Distributed verification and hardness of distributed approximation

Atish Das-Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer · 2012

Cited alongside, same era.

“Tri, Tri Again”: Finding triangles and small subgraphs in a distributed setting

Danny Dolev, Christoph Lenzen, and Shir Peled · 2012

Cited alongside, same era.

Local decision and verification with bounded-size outputs

Heger Arfaoui, Pierre Fraigniaud, and Andrzej Pelc · 2013

Cited alongside, same era.

On the power of the congested clique model

Andrew Drucker, Fabian Kuhn, and Rotem Oshman · 2014

Later among the works it cites.

On the number of opinions needed for fault-tolerant run-time monitoring in distributed systems

Pierre Fraigniaud, Sergio Rajsbaum, and Corentin Travers · 2014

Later among the works it cites.

Near-constant-time distributed algorithms on a congested clique

James W. Hegeman, Sriram V. Pemmaraju, and Vivek Sardeshmukh · 2014

Later among the works it cites.

Solving the induced subgraph problem in the randomized multiparty simultaneous messages model

Jarkko Kari, Martin Matamala, Ivan Rapaport, and Ville Salo · 2014

Later among the works it cites.

Roth’s theorem in many variables

Tomasz Schoen and Ilya D. Shkredov · 2014

Later among the works it cites.

Allowing each node to communicate only once in a distributed system: shared whiteboard models