Dept Banner
Dept Banner


Download as iCal file

Discrete Math

Proof of an entropy conjecture of Leighton and Moitra

Pat Devlin: Rutgers University

Location:  Hill 705
Date & time: Monday, 20 February 2017 at 2:00PM - 2:11PM

Suppose F is a random (not necessarily uniform) permutation of {1, 2, ... , n} such that |Prob(F(i) < F(j)) -1/2| > epsilon for all i,j. We show that under this assumption, the entropy of F is at most (1-delta)log(n!), for some fixed delta depending only on epsilon [proving a conjecture of Leighton and Moitra]. In other words, if (for every distinct i,j) our random permutation either noticeably prefers F(i) < F(j) or prefers F(i) > F(j), then the distribution inherently carries significantly less uncertainty (or information) than the uniform distribution.Our proof relies on a version of the regularity lemma, a combinatorial bookkeeping gadget, and a few basic probabilistic ideas. The talk should be accessible for any background, and I'll gently recall any relevant notions (e.g., entropy) as we go. Those dissatisfied with the talk will not be refunded the cost of admission, and those tremendously dissatisfied won't like my defense either.This is from a recent paper joint with Huseyin Acan and Jeff Kahn.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530