[Colloquium] 4/22 Research at TTIC: Yury Makarychev, TTIC

[Mary Marre]

When:     Friday, April 22nd at noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:      Yury Makarychev, TTIC


Title:      Satisfiability of Ordering CSPs Above Average



Abstract:

We study the satisfiability of ordering constraint satisfaction problems
(CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich,
and Yeo that the satisfiability above average of ordering CSPs of arity k
is fixed-parameter tractable for every k. Previously, this was only known
for k=2 and k=3. We also generalize this result to more general classes of
CSPs, including CSPs with predicates defined by linear inequalities.



To obtain our results, we prove a new Bonami-type inequality for the
Efron-Stein decomposition. The inequality applies to functions defined on
arbitrary product probability spaces. In contrast to other variants of the
Bonami Inequality, it does not depend on the mass of the smallest atom in
the probability space. We believe that this inequality is of independent
interest.




This talk is based on a joint work with Konstantin Makarychev and Yuan Zhou.



********************************************************************

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at mcallester at ttic
.edu




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757 <%28773%29%20834-1757>*
*f: (773) 357-6970 <%28773%29%20357-6970>*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160419/b0c4e5cc/attachment.htm