ARC Colloquium: William Gasarch - University of Maryland at College Park

Event Details

Dani Denton
denton at cc dot gatech dot edu



Summary Sentence: Klaus 1116 East at 1 pm

Full Summary: No summary paragraph submitted.

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)

Advanced Results in the Theory of Languages and Computation which have Simple Proofs

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!

  1. 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!
  2. 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!
  3. It is easy to show that COL3 \le COL4 (three-colorability \le 4-colorablity). Is COL4 \le COL3? You probably know that it is by going through the Cook-Levin 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!

Additional Information

In Campus Calendar

ARC, College of Computing, School of Computer Science

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Jan 14, 2016 - 10:29am
  • Last Updated: Apr 13, 2017 - 5:17pm