Date & Time:
March 29, 2022 3:30 pm – 4:30 pm
Location:
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
03/29/2022 03:30 PM 03/29/2022 04:30 PM America/Chicago Yufei Zhao (MIT) – Enumerating k-SAT functions Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

How many k-SAT functions on n boolean variables are there? What does a typical such function look like? Bollobás, Brightwell, and Leader conjectured that for each fixed k, almost every k-SAT function is unate. In this talk, I will discuss progress towards this conjecture and explain how the hypergraph container method can be used to reduce the problem to a hypergraph Turán-like problem, which is solved for k ≤ 4 but remains open in general.

Joint work with Dingding Dong and Nitya Mani

Host: Alexander Razborov

Speakers

Yufei Zhao

Assistant Professor, Massachusetts Institute of Technology

Yufei Zhao is Assistant Professor of Mathematics at the Massachusetts Institute of Technology. He received his PhD from MIT in 2015 and has previously held positions at Oxford, Berkeley, Stanford, and Microsoft Research. He has been awarded the SIAM Dénes Kőnig prize (2018), the Sloan Research Fellowship (2019), and the NSF CAREER Award (2021). His research tackles a broad range of problems in discrete mathematics, including extremal, probabilistic, and additive combinatorics, graph theory, and discrete geometry, as well as applications to computer science.

Related News & Events

Haifeng Xu
UChicago CS News

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022
UChicago CS News

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022
UChicago CS News

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022
UChicago CS News

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022
UChicago CS News

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022
In the News

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022
In the News

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022
UChicago CS News

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022
UChicago CS News

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022
UChicago CS News

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022
In the News

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
UChicago CS News

In-Fridge Controller Could Scale Up Quantum Computers, Award-Winning UChicago Research Finds

Jan 10, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube