FLAC What's New

Homework 5 Solutions Posted

2012-02-29T10:40:00.000-08:00

Homework 6, Problem 4 Clarification

2012-02-29T10:19:00.002-08:00

In problem 4 you should assume that the input of a Turing Machine M is always a binary string (the input alphabet is {0,1}).

Homework 5 Typo

2012-02-27T14:08:00.003-08:00

There was a small typo in problem 1(B=>t_kBa_k should have been B=>b_kBa_k). The problem has been corrected on the web site.

Homework 4 (Solutions Correction)

2012-02-25T15:32:00.001-08:00

There was an error in the Turing machine diagram for the Problem 1 solution. The figure has been corrected, and an updated PDF of the solutions was uploaded this afternoon. Sorry for the confusion!

Project Advisors

2012-02-22T20:42:00.000-08:00

Greg
Chase Brownell
Will Devanny
Wade Gordon
Max Illfelder
Joseph Lee
Kellie Medlin
Laura Scharff

Jeremiah
Igor Balla
Rick Benua
Eric Cheek
Alex Crichton
Robert Liu
Paul Schultz
Max Tucker

Lenore
Ved Basu
Andrew Israel
Jason MacDonald
William Macrae
Mohith Muddasani
Sanjeev Reddy
Divya Sharma

Homework 3 (Revised Hint)

2012-02-02T11:39:00.000-08:00

We had originally intended for the state "101" in problem 1(b) to be an accept state. For problem 1(b) you may either
(1) minimize the original DFA (presented in the homework).
(2) minimize the new DFA (after changing "101" to an accept state).

You will be given full credit for either answer. We will assume that you are minimizing the original DFA (option 1) unless clearly indicated.

Note: If you have not solved the problem yet (or even if you have) we would recommend minimizing the new DFA. The hint for homework 3 problem 2 will make more sense if you make "101" an accept state.

Monday Office Hours Moved to NSH 1505

2012-01-26T10:35:00.000-08:00

The super office hours (Monday 3:30-5:30 PM) have been relocated to NSH 1505 for the rest of the semester. Formerly, the problem solving session was held in GHC 2109.

Homework 1

2012-01-18T22:07:00.001-08:00

There are two minor errors in Homework 1. In Problem 1(b), "0", "1", and "2" should be called "digits", not letters. In the definition of min(A) in Problem 2, both instances of "L" should be "A" instead. The homework PDF was modified to reflect these corrections as of 11:30 p.m. on Wednesday, Jan. 18.

Fun Applications of the Pigeonhole Principle

2012-01-18T08:37:00.000-08:00

http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/

Example Homework Solution

2012-01-17T11:31:00.000-08:00

Here is an example of a well writen homework solution. The answer references problem 1.32 in Sipser (Problem 1.25 in the old edition of Sipser).

Apologies about the formatting. You can right click on the image and select view image.

Project Ideas

2011-12-15T11:20:00.000-08:00

Below are some papers that would be very nice class projects.

Smooth Sensitivity and Sampling in Private Data Analysis by K. Nissim, S. Raskhodnikova and A. Smith (STOC 2007)

Terminal Backup, 3D Matching, and Covering Cubic Graphs by E. Anshelevich and A. Karagiozova (STOC 2007).

Resolving the Complexity of Some Data Privacy Problems by J. Blocki and R. Williams (ICALP 2010).

Simple Deterministic Approximation Algorithms for Counting Matchings by M. Bayati, D. Gamarnik,D. Katz, C. Nair and P. Tetali (STOC 2007).

Fully Homomorphic Encryption over the Integers by M.van Dijk, C. Gentry, S. Halevi and V.Vaikuntanathan (IACR 2010).

Regret Minimization and the Price of Total Anarchy by Avrim Blum, MohammadTaghi Hajiaghayi, Katrina Ligett and Aaron Roth (STOC 2008).

A Learning Theory Approach to Non-Interactive Database Privacy by Avrim Blum, Katrina Ligett and Aaron Roth (STOC 2008).

Evolvability from Learning Algorithms by Vitaly Feldman (STOC 2008).

Delegating Computation: Interactive Proofs for Muggles by Shafi Goldwasser,
Yael Tauman Kalai and Guy N. Rothblum (STOC 2008).

A Constructive Proof of the Lavasz Local Lemma by R. Moser (STOC 2009).

Approximating edit distance in near linear time by A. Andoni and K. Onak (STOC 2009).

Public-key cryptosystems from the worst-case shortest vector problem: extended abstract by Chris Peikert (STOC 2009).

Finding, minimizing, and counting weighted subgraphs by V. Vassilevska and R. Williams (STOC 2009).

Perfect matchings in o(n log n) time in regular bipartite graphs by Ashish Goel, Michael Kapralov and Sanjeev Khanna (STOC 2010).

Public-key cryptography from different assumptions by Benny Applebaum, Boaz Barak and Avi Wigderson (STOC 2010).

Improving exhaustive search implies superpolynomial lower bounds by Ryan Williams (STOC 2010).

Interactive privacy via the median mechanism by Aaron Roth and Tim Roughgarden (STOC 2010).

A full derandomization of schöning's k-SAT algorithm by Robin A. Moser and Dominik Scheder (STOC 2011).

Stability Yields a PTAS for k-Median and k-Means Clustering by Awasthi, P. Blum, A. and Sheffet, O (FOCS 2010).

Helpful Links

2011-12-15T08:40:00.000-08:00

· The Wiki for FSM's with lots of neat links.

· Mor Harchol-Balter's notes on applying to grad school in computer science.

· Electronic version of the proceedings of STOC

· Electronic version of the proceedings of FOCS.