Summer, 2014
Students
Naomi Becker (Macalester College): Working on Cloud Computing.
Jassiem Ifill (Morehouse): Working on Cloud Computing.
Frederic Koehler (Princeton. Unoffical): Approximation Algorithms for Scheduling.
Aaron Lowe (Haverford): Working on Crypto.
Dao Lu (Princeton)): Working on Ramsey Games.
Daniel Pareja (Kean College): Working on Finding Patterns in Data.
Matthew Das Sarma (Mont. Blair HS. Unoffical): Approximating vertex covers with hard capacities.
Lynesia Taylor (Spelman): Working on Crypto.
Prayas Timalsina (Claflin University): Working on Finding Patterns in Data.
Ellen Vitercik (Columbia): Working on Crypto.
Eric Weaver (Grove City College): Working on Ramsey Games.
Natalie Wilkerson (Roanoke College): Working on Ramsey Games.
Projects
Security in Cloud Computing
Mentors: Elaine Shi, Jonathan Katz
Cloud computing has allowed users and organizations to outsource their storage and computation to thirdparty cloud service providers. When the thirdparty server is untrusted, an important security challenge is how a client can verify that the server has stored the data and performed the computation correctly. This project will look at this using both algorithmic and cryptographic tools and be a blend of theory and practice.
Improving Upper and Lower Bounds via Games
Mentors: William Gasarch, Clyde Kruskal
The following is a well known: There exist a number G such that, for all 2colorings of the GxG grid, there is a square with all 4 colors the same color. The best known upper bound on G are INSANE!!!! The lower bounds that are known are quite far from the upper bounds. We will try to get better bounds on G by viewing coloring as a game. Two players alternate coloring (say) 12x12 with R and B, both trying to avoid getting a square in their color. Good strategies for both players may lead to tie games and hence colorings. This is just one problem. There are many problems in the field of combinatorics known as Ramsey Theory that we will try to tackle via games. The work will use combinatorics and AI game techniques.
Theory and Practice of Password Cracking via Rainbow Tables
Mentor: Jonathan Katz
Rainbow tables are used by such tools as “John the Ripper” for passwordcracking attacks on hashed passwords in the real world. This project will study the performance of rainbow tables from both theoretical and practical points of view. Depending on the interests of the student, this project could include 
(1) Deriving optimal (theoretical) bounds on the performance of rainbow tables in classical and novel settings
(2) Experimentally verifying known bounds on the performance of rainbow tables, and/or understanding and optimizing existing implementations, or
(3) Extending rainbow tables to cracking other cryptographic primitives.
