research
∙
04/04/2023
Strong spatial mixing for colorings on trees and its algorithmic applications
Strong spatial mixing (SSM) is an important quantitative notion of corre...
share
research
∙
09/11/2022
Nearly all k-SAT functions are unate
We prove that 1-o(1) fraction of all k-SAT functions on n Boolean variab...
research
∙
07/06/2022
From algorithms to connectivity and back: finding a giant component in random k-SAT
We take an algorithmic approach to studying the solution space geometry ...
research
∙
05/24/2022
On the number of error correcting codes
We show that for a fixed q, the number of q-ary t-error correcting codes...
research
∙
04/05/2022
Extremal results on feedback arc sets in digraphs
A directed graph is oriented if it can be obtained by orienting the edge...
research
∙
08/09/2021
An Interpretable Approach to Hateful Meme Detection
Hateful memes are an emerging method of spreading hate on the internet, ...
research
∙
02/20/2021
Making an H-Free Graph k-Colorable
We study the following question: how few edges can we delete from any H-...
research
∙
05/08/2019