Seminario Interdipartimentale di Algoritmica
 
 
 

ore 11 Hansel's Theorem and Koerner's Graph Entropy
Prof. Jaikumar Radhakrishnan
TIFR, Mumbai

ore 12 Meccanica statistica dei problemi di ottimizzazione combinatoria
Dott. Federico Ricci Tersenghi ,
Dipartimento di Fisica, La Sapienza di Roma

Dipartimento di Scienze dell'Informazione - DSI
via Salaria 113, III piano
Aula Seminari

Abstract (Radhakrishnan): We consider the following theorem of Hansel:

Suppose G_1, G_2,....,G_t are bipartite graphs whose union is the complete graph on n vertices. Let n_i be the number of non-isolated vertices in G_i. Then, \sum_{i=1}^t n_i >= n \log_2 n.

We will present two proofs of this theorem, the first, due to Hansel, based on a counting argument, and the second, due to Pippenger, based on information theoretic considerations. By analyzing these proofs, we will arrive at two equivalent definitions of Koerner's graph entropy.

Hansel's theorem was originally proved for showing lower bounds on the size of AND-OR circuits computing threshold functions. We will describe this application.

Abstract (Ricci-Tersenghi): In questo seminario verra' illustrato come tecniche di meccanica statistica dei sistemi disordinati possono essere usate per lo studio di ensemble random di problemi di ottimizzazione combinatoria (quale ad esempio la random 3-SAT). In particolare, presentero` la soluzione al problema della random 3-XORSAT che, sebbene piu` semplice della random 3-SAT, mostra una simile transizione SAT/UNSAT . In questo contesto mostrero` il legame che esiste tra la transizione SAT/UNSAT, la transizione termodinamica e una transizione percolativa negli ipergrafi random.