[Colloquium] REMINDER: 5/31 Research at TTIC: Madhur Tulsiani, TTIC

[Alicia McClarin]

*When:*     Friday, May 31st. Refreshments at noon. Talk begins at 12:20pm.

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

*Who: *      Madhur Tulsiani, TTIC

*Title: *       CSPs and Expansion

*Abstract: *Constraints Satisfaction Problems (CSPs) play an important role
in the theory of approximability. They provide an important benchmark
combinatorial optimization problem for algorithms, as well as equivalent
formulations of questions about Probabilitically Checkable Proofs (PCPs)
which are used to prove lower bounds on approximability.

It is relatively well understood that if an instance of a 2-CSP (having two
variables in each constraint) is considered as a graph, then the expansion
of this graph can be exploited by approximation algorithms - I will discuss
some instances of this which led to new algorithms in the past.

I will also discuss new notions of expansion (for hypergraphs) defined
recently (known as high-dimensional expansion) which can be exploited by
algorithms for k-CSPs for k > 2. I will also discuss applications of these
algorithmic results to questions in coding theory.

Most of the new results I will discussed are based on joint works with
Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank
Srivastava.

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

*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 Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>.

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 518*
*Chicago, IL 60637*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190531/2a321bda/attachment-0001.html>