2004-2005 seminars

I will sketch a proof that for any monotone graph property P and any $\epsilon >0$ one can approximate efficiently the minimum number of edges that have to be deleted from an n-vertex input graph to get a graph that satisfies P, up to an additive...

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and...

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. Extractors have proved useful in a variety of seemingly unrelated areas. We construct new extractors which...

We study the following problem regarding quadratic programs: Given a quadratic polynomial \sum a_{xy} xy, where all a_{xx} = 0, find a -1,+1 assignment to its variables that maximizes it. This problem recently attracted attention due to its...

A ranking of n web pages is to be chosen from outputs of k search engines. How do we choose one ranking minimizing the "disagreement" with the k rankings? A clustering of n genes is to be chosen from outputs of k clustering algorithms. How do we...

A graph is called {\em even-hole-free} if no induced subgraph of it is a cycle with an even number of vertices. A vertex of a graph is {\em bisimplicial} if the vertex set of its neighborhood can be partitioned into two cliques. Bruce Reed...

Given a hypergraph H=(V,E), its conflict-free chromatic number (CF-chromatic number) is the minimum number of colors needed to color the vertex set V such that, for every hyperedge S, there is at least one element v \in S whose color is unique (in S...

We present the Controlled Linear Programming Problem (CLPP), a new combinatorial optimization problem nicely merging linear programming with games. In a system of linear monotone constraints of the form $x_i\leq p_i^j(\bar x)+w_i^j$, where $p_i^j$...

The well-known Max Cut problem asks for the largest bipartite subgraph of a graph G. This problem has been the subject of extensive research, both from the algorithmic perspective in computer science and the extremal perspective in combinatorics...

Standard information-theoretic results show that data over small, typically binary, alphabets can be compressed to Shannon's entropy limit. Yet most practical sources, such as text, audio, or video, have essentially infinite support. Compressing...