All reports by Author Michael Langberg:

__
TR16-130
| 11th August 2016
__

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra#### Tight Network Topology Dependent Bounds on Rounds of Communication

__
TR03-076
| 8th September 2003
__

Michael Langberg#### Testing the independence number of hypergraphs

__
TR00-043
| 21st June 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### A Note on Approximating MAX-BISECTION on Regular Graphs

__
TR00-021
| 19th April 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### Improved Approximation of MAX-CUT on Graphs of Bounded Degree

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

Michael Langberg

A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

Uriel Feige, Marek Karpinski, Michael Langberg

We design a $0.795$ approximation algorithm for the Max-Bisection problem

restricted to regular graphs. In the case of three regular graphs our

results imply an approximation ratio of $0.834$.

Uriel Feige, Marek Karpinski, Michael Langberg

We analyze the addition of a simple local improvement step to various known

randomized approximation algorithms.

Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently

known for the Max Cut problem on general graphs~\cite{GW95}.

We consider a semidefinite relaxation of the Max Cut problem,

round it using the ...
more >>>