Fooling views: a new lower bound technique for distributed computations under congestion (Q2220402)

From MaRDI portal

Revision as of 09:12, 24 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Fooling views: a new lower bound technique for distributed computations under congestion	scientific article

Statements

scholarly article

0 references

Fooling views: a new lower bound technique for distributed computations under congestion (English)

0 references

0 references

Keren Censor-Hillel

0 references

0 references

Christoph Lenzen

0 references

Distributed Computing

0 references

publication date

22 January 2021

0 references

full work available at URL

https://arxiv.org/abs/1711.01623

0 references

MaRDI profile type

MaRDI publication profile

0 references

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

0 references

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

0 references

A fast and simple randomized parallel algorithm for the maximal independent set problem

0 references

0 references

A trade-off between information and communication in broadcast protocols

0 references

0 references

Randomized Proof-Labeling Schemes

0 references

Span programs for functions with constant-sized 1-certificates

0 references

Listing Triangles

0 references

A lower bound for the distributed Lovász local lemma

0 references

Quantum Algorithms for Element Distinctness

0 references

Fast distributed algorithms for testing graph properties

0 references

Algebraic methods in the congested clique

0 references

Distributed construction of purely additive spanners

0 references

Speeding up the Four Russians Algorithm by About One More Logarithmic Factor

0 references

Distributed Triangle Detection via Expander Decomposition

0 references

Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration

0 references

Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication

0 references

“Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting

0 references

On the power of the congested clique model

0 references

A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities

0 references

On extremal problems of graphs and generalized graphs

0 references

Distributed testing of excluded subgraphs

0 references

0 references

0 references

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

0 references

Finding a Minimum Circuit in a Graph

0 references

Triangle Finding and Listing in CONGEST Networks

0 references

0 references

Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model

0 references

Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication

0 references

Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

0 references

Local Computation

0 references

Communication Complexity

0 references

Powers of tensors and fast matrix multiplication

0 references

0 references

Quantum algorithm for triangle finding in sparse graphs

0 references

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

0 references

Improved distributed steiner forest construction

0 references

Locality in Distributed Graph Algorithms

0 references

A Simple Parallel Algorithm for the Maximal Independent Set Problem

0 references

Quantum Algorithms for the Triangle Problem

0 references

An optimal bit complexity randomized distributed MIS algorithm

0 references

A tight unconditional lower bound on distributed randomwalk computation

0 references

A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring

0 references

What Can be Computed Locally?

0 references

Brief Announcement

0 references

A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees

0 references

Distributed Computing: A Locality-Sensitive Approach

0 references

A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction

0 references

On the distributional complexity of disjointness

0 references

Distributed Verification and Hardness of Distributed Approximation

0 references

Experimental and Efficient Algorithms

0 references

Multiplying matrices faster than coppersmith-winograd

0 references

Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)

0 references

An improved combinatorial algorithm for Boolean matrix multiplication

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/s00446-020-00373-4

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2220402

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2220402&oldid=36647140"