Nearly all k-SAT Functions are Unate

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=3qO66qkVTlo


Duration: 1:04:40
773 views
11

Yufei Zhao (Massachusetts Institute of Technology)
https://simons.berkeley.edu/talks/yufei-zhao-massachusetts-institute-technology-2023-07-24
Structural Results

We prove that 1-o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003. (Joint work with József Balogh, Dingding Dong, Bernard Lidický, and Nitya Mani).



Other Videos By Simons Institute for the Theory of Computing


2023-07-27Sign-rank vs Margin
2023-07-27Tight Space Complexity of the Coin Problem
2023-07-27A New Upper Bound for the Heilbronn Triangle Problem
2023-07-26A Polynomial Bogolyubov type Result for the Special Linear Group
2023-07-26Higher-dimensional Expansion of Random Geometric Complexes
2023-07-26Testing Thresholds for High-dimensional Sparse Random Geometric Graphs
2023-07-25An Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension
2023-07-25Larger Corner-free Sets in High Dimensions
2023-07-25Top-Down Lower Bounds for Depth-Four Circuits
2023-07-25P-smallness of Increasing Families
2023-07-24Nearly all k-SAT Functions are Unate
2023-07-21Session #3
2023-07-20Survey on Optimization in FL
2023-07-20Session #2
2023-07-20Survey on Privacy/Security in FL
2023-07-20Session #1
2023-07-19Keynote
2023-07-19Another Round Of Breaking and Making Quantum Money: How to Not Build It From Lattices and More
2023-07-19Applications of Bit Commitments in a Quantum World
2023-07-19Pseudorandomness: From Quantum States to Binary Strings
2023-07-19Introduction to Quantum Cryptography Without One-Way Functions


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Structural Results
Yufei Zhao