Combinatorics and Algorithms for Real Problems

Home
Prior REU Programs
Prior REU Programs Testimonials
Prior Students- Where now?
Prior REU's- papers

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.

Group Photo!

Projects

  • Security in Cloud Computing
    Mentors: Elaine Shi, Jonathan Katz

    Cloud computing has allowed users and organizations to outsource their storage and computation to third-party cloud service providers. When the third-party 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.

  • Identifying Patterns in Data Graphs
    Mentor: Louiqa Raschid

    Linked Data and Bigdata have made available many interesting datasets. Annotation graph datasets are interesting since they capture rich human knowledge through annotations or links from scientific concepts to terms in ontologies. The challenge is to find interesting and novel patterns in annotation datasets and to visualize the patterns so scientists can utilize the patterns. Applications range from predicting gene function to finding new targets for drugs.

  • 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 2-colorings 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 password-cracking 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.