- Series
- Combinatorics Seminar
- Time
- Friday, September 7, 2012 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Will Perkins – School of Mathematics, Georgia Tech
- Organizer
- Prasad Tetali
We study an Achlioptas-process version of the random k-SAT process: a
bounded number of k-CNF clauses are drawn uniformly at random at each step,
and exactly one added to the growing formula according to a particular
rule. We prove the existence of a rule that shifts the satisfiability
threshold. This extends a well-studied area of probabilistic combinatorics
and random graphs to random CSP's. In particular, while a rule to delay
the 2-SAT threshold was known previously, this is the first proof of a rule
to shift the threshold of a CSP that is NP-hard. We then propose a gap
decision problem based upon this semi-random model with the aim of
investigating the hardness of the random k-SAT decision problem.