[Colloquium] Re: REMINDER: 2/3 Research at TTIC: Li-Yang Tan, TTIC

[Mary Marre via Colloquium]

When:     Friday, February 3rd at noon



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



Who:       Li-Yang Tan, TTIC


Title: Computational complexity through the lens of circuits, proofs, and
randomness

Abstract: Computational complexity theory is rooted in many of computer
science's most fascinating questions.  Three examples of such questions
are: Are there functions that are simple to describe, and yet require large
circuits to compute?  Are there short mathematical theorems that require
lengthy proofs?  Does every efficient randomized algorithm have an
efficient deterministic counterpart?

In this talk I will describe results motivated by and contributing to our
understanding of these questions, focusing on three results:

(1) An average-case depth hierarchy theorem for boolean circuits, which
resolves a thirty-year-old conjecture in circuit complexity;

(2) Exponentially-improved lower bounds for the Frege proof system, the
canonical proof system for propositional logic;

(3) The fastest deterministic algorithm for finding satisfying assignments
of CNF formulas that have many such assignments, a basic unresolved problem
in derandomization.

These results illuminate rich connections among the respective subfields of
complexity theory --- circuit complexity, proof complexity, and
pseudorandomness --- and also have implications to areas outside of
complexity theory, such as parallel computing and SAT solving.  I will also
touch on how the techniques we have developed point to avenues for progress
on a few flagship challenges of complexity theory.

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

*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>


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*

On Thu, Feb 2, 2017 at 2:22 PM, Mary Marre <mmarre at ttic.edu> wrote:

> When:     Friday, February 3rd at noon
>
>
>
> Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
>
>
>
> Who:       Li-Yang Tan, TTIC
>
>
> Title: Computational complexity through the lens of circuits, proofs, and
> randomness
>
> Abstract: Computational complexity theory is rooted in many of computer
> science's most fascinating questions.  Three examples of such questions
> are: Are there functions that are simple to describe, and yet require large
> circuits to compute?  Are there short mathematical theorems that require
> lengthy proofs?  Does every efficient randomized algorithm have an
> efficient deterministic counterpart?
>
> In this talk I will describe results motivated by and contributing to our
> understanding of these questions, focusing on three results:
>
> (1) An average-case depth hierarchy theorem for boolean circuits, which
> resolves a thirty-year-old conjecture in circuit complexity;
>
> (2) Exponentially-improved lower bounds for the Frege proof system, the
> canonical proof system for propositional logic;
>
> (3) The fastest deterministic algorithm for finding satisfying assignments
> of CNF formulas that have many such assignments, a basic unresolved problem
> in derandomization.
>
> These results illuminate rich connections among the respective subfields
> of complexity theory --- circuit complexity, proof complexity, and
> pseudorandomness --- and also have implications to areas outside of
> complexity theory, such as parallel computing and SAT solving.  I will also
> touch on how the techniques we have developed point to avenues for progress
> on a few flagship challenges of complexity theory.
>
> ************************************************************
> ********************************************************
>
> *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>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 504*
> *Chicago, IL  60637*
> *p:(773) 834-1757 <(773)%20834-1757>*
> *f: (773) 357-6970 <(773)%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/20170203/68a835a7/attachment.html>