Algorithms & Randomness Center (ARC)
William Gasarch – University of Maryland
Wednesday, February 17, 20116
Klaus 1116 East  1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Advanced Results in the Theory of Languages and Computation which have Simple Proofs
Abstract:
Automata theory is about the following: Given a language (a set of strings) how hard is it? Is it regular, context free, or decidable? We give three results that COULD be put in a course on such but are not!
 Regular, Context free, and Decidable languages are closed under many operations. Note the following: if L is regular (CFL) then SUBSEQ(L) is regular (CFL). This is an easy exercise. But what if L is decidable? Is SUBSEQ(L) decidable? The answer may surprise you!
 There are languages L that are regular but the DFA for them is much smaller than the CFG for them. How much smaller? The answer may surprise you!
 It is easy to show that COL3 \le COL4 (threecolorability \le 4colorablity). Is COL4 \le COL3? You probably know that it is by going through the CookLevin Theorem. Is there an easier proof? The answer would surprise you if I didn't ask the question so I'll just say YES I will show COL4 \le COL3 with a simple proof.
The answers may surprise you!
 In Campus Calendar

No
 Groups

ARC, College of Computing, School of Computer Science
 Invited Audience

Undergraduate students, Faculty/Staff, Public, Graduate students
 Categories

Seminar/Lecture/Colloquium
 Keywords

Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech
 Status

 Created By: Dani Denton
 Workflow Status: Published
 Created On: Jan 14, 2016  10:29am
 Last Updated: Apr 13, 2017  5:17pm