Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Benny Sudakov:

TR16-086 | 29th May 2016
Noga Alon, Klim Efremenko, Benny Sudakov

Testing Equality in Communication Graphs

Revisions: 1

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose
that on each vertex of the graph there is a player having an $n$-bit
string. Each player is allowed to communicate with its neighbors according
to an agreed communication protocol, and the players must decide,
deterministically, if their inputs ... more >>>

TR10-037 | 8th March 2010
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time ... more >>>

TR10-026 | 25th February 2010
Hao Huang, Benny Sudakov

A counterexample to the Alon-Saks-Seymour conjecture and related problems

Consider a graph obtained by taking edge disjoint union of $k$ complete bipartite graphs.
Alon, Saks and Seymour conjectured that such graph has chromatic number at most $k+1$.
This well known conjecture remained open for almost twenty years.
In this paper, we construct a counterexample to this
conjecture and discuss ... more >>>

ISSN 1433-8092 | Imprint