[Theory] UC Theory Seminar

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, March 29, 3:30pm
Location TBA

Yufei Zhao (MIT)

TITLE:  Enumerating k-SAT functions

ABSTRACT: 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.

%%%%%%%%%%%%%%%%%%%%%%%
While the University no longer requires wearing masks, we will set aside a couple of tables designated "masks required".
%%%%%%%%%%%%%%%%%%%%%%%

Yufei will give another talk at the Math Colloquium on March 30, see

https://mathematics.uchicago.edu/events/event/1471/

for details. 


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220322/4dd94d15/attachment.html>