AMSC 689: RIT on Complexity Theory

Spring of 2009 and Fall of 2009

RIT stands for Research Interaction Team. These are classes where students get to interact with faculty. They are usually seminars.

This will be an RIT focusing on Complexity Theory. Our main focus at the beginning will be bit-probe complexity.

During SPRING 2009 it was Wedensday 1:00-2:00 in AV Williams 3258 (Except when noted).

During FALL 2009 (NOW!) it is Wedensday 2:00-3:00 in AV Williams 3258 (Except when noted).

SCHEDULE OF TALKS

1. Feb 4, 2009. The Bit Probe Model. Bill Gasarch. Used notes from 752. BITPROBENOTES.PDF, BITPROBENOTES.PS. Notes by Bill Gasarch. (Just did the easy upper bound.)
2. Feb 11, 2009. A Randomized One-sided Error Scheme for Membership. Russell Moriarity. Used PAPER Are Bit Vectors Optimal by Buhrman, Miltersen, Radhakrishnan, Venkatesh BITVECTOPT.PDF, BITVECTOPT.PS.
3. Feb 18, 2009. Another Randomized One-sided Error Scheme for Membership. Russell Moriarity. Used BITVECTOR paper.
4. Feb 25, 2009. Canonical Ramsey Theory. Bill Gasarch. (Sorry- no notes.)
5. Mar 4, 2009. Easy Lower Bounds in the Bit Probe Model. Amy Alford. Used BIT PROBE NOTES.
6. Mar 11, 2009. Lower Bounds in the One-sided-error Bit Probe Model. Russell Moriarity. (NOTE- Mar 18 is during spring break so no talk.)
7. Mar 25, 2009. TWO lectures! Sane bounds on the Poly VDW numbers- Justin Kruskal. Randomized Two-sided Error Scheme for Membership- Part I. Russell Moriarity. Uses BITVECTOR paper.
8. April 1, 2009 Randomized Two-sided Error Scheme for Membership- Part II. Russell Moriarity. Uses BITVECTOR paper.
9. April 8, 2009 Two lectures. Pre-RSA Crypto by Rahul. Graphs with high girth and chromatic number by Gasarch
10. April 15 2009. Should Tables be Sorted. Amy Alford. Used PAPER Should Tables be Sorted by Andy Yao TABLES.PDF, or notes on this paper by Bill Gasarch. CELLYAO.PDF, (NOTE: This talk will be 1:30-2:30)
11. April 22 2009. Membership in O(1). Wow! Peter Fontana. Paper: FKS.PDF. Notes: FKS-NOTES.PDF.
12. Speedup for co-NP complete problems and noncomputability. Hunter Monroe. COHPB.PDF
13. May 6 2009 Bit probe lower bounds for Succinct Data Structures. Marius Zimand. Used PAPER Bit probe lower bounds for Succinct Data Structures by Viola. TRIZ.PDF,
14. Sept 9, 2009. A Randomized Algorithm for k-CNF SAT. Talk by William Gasarch. Result by Robin Moser. (Sorry, no notes.)
15. Sept 16 2009. Constructing graphs with large girth and chromatic numbre 6 or 9 or 12.
16. Sept 23 2009. A Randomized Algorithm for k-CNF SAT- IMPROVED! By Richard Beigel.
17. Sept 30 2009. Time Space Tradeoffs for SAT. By Peter Fontana. SATLOWERBOUNDPRES.PDF,
18. Oct 7 2009. Time Space Tradeoffs for SAT II. By Russell Moriarity.
19. Oct 21 2009. Turans Theorem and points in the plane: Two elegant proofs. by William Gasarch.
20. Nov 11 2009. Adiabatic Quantum Computation. By Vicky Choi. VICKY-CHOI-WEBSITE-WHICH-HAS-SLIDES

PAPERS we may look at later:

1. On the Power of Two, Three, or Four Probes by Alon and Feige. 234PROBES.PDF,
2. Error Correcting Data Structures by Ronald de Wolf. ERRORCORRECT.PDF
3. Cell Probe Lower Bounds for Succinct Data Structures by Alexander Golynski. CELLPROBE-SODA2009.PDF
4. On Data Structures and Asymetric Communication Complexity by Peter Bro Milterson and Noam Nisan and Shmuel Safra and Avi Wigderson. ASYM.PDF