All reports by Author Benny Sudakov:

__
TR16-086
| 29th May 2016
__

Noga Alon, Klim Efremenko, Benny Sudakov#### Testing Equality in Communication Graphs

Revisions: 1

__
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

__
TR10-026
| 25th February 2010
__

Hao Huang, Benny Sudakov#### A counterexample to the Alon-Saks-Seymour conjecture and related problems

Noga Alon, Klim Efremenko, Benny Sudakov

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 >>>

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

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 >>>

Hao Huang, Benny Sudakov

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 >>>