Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MAXIMUM MATCHING:
Reports tagged with maximum matching:
TR16-111 | 20th July 2016
Amit Chakrabarti, Sagar Kale

Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

We develop a paradigm for studying multi-player deterministic communication,
based on a novel combinatorial concept that we call a {\em strong fooling
set}. Our paradigm leads to optimal lower bounds on the per-player
communication required for solving multi-player $\textsc{equality}$
problems in a private-message setting. This in turn gives a ... more >>>


TR19-101 | 24th July 2019
Amit Chakrabarti, Prantar Ghosh

Streaming Verification of Graph Computations via Graph Structure

We give new algorithms in the annotated data streaming setting---also known as verifiable data stream computation---for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to ... more >>>


TR20-100 | 6th July 2020
Amit Chakrabarti, Prantar Ghosh, Justin Thaler

Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that ... more >>>




ISSN 1433-8092 | Imprint