Summer, 2015
Projects
The Can't Stop Game
Mentor: Clyde Kruskal
The game Can't Stop depends on a combination of luck and skill. In this game a player rolls dice to get ahead, but can stop. If he doesn't stop in time he may lose all that he has gained that turn. For more on the game, including the rules, see here.
Monte Carlo techniques or game playing are ideal to study this game. We will learn these techniques and write programs to play the game well. We will then try to learn what the programming is really doing to make conjectures and prove theorems.
For a talk on research Clyde Kruskal (and co-authors) have already done on the 1-player version see here.
Using SAT Solvers to find Ramsey Numbers
Mentor: William Gasarch
The following is well known: If there are 6 people at a party then either 3 all know each other, or 3 all DO NOT know each other. More mathematically one could say that no matter how you 2-color the edges of the complete graph on 6 vertices, there is a monochromatic triangle. This is not true for the complete graph on 5 vertices.
There are many such theorems. For some of them the exact cutoffs are not know. In this project you will learn 1) How to phrase these kinds of questions in terms of Boolean Formulas 2) Some fast algorithms for trying to find a satisfying assignment for a Boolean Formula 3) Use (1) and (2) to try to find more exact numbers for types of Ramsey Numbers.
Hence we will be applying SAT algorithms to Ramsey Theory!
For a talk about algorithms for SAT see here.
Pricing Over Social Networks
Mentor: MohammadTaghi Hajiaghayi
Despite the rapid growth, online social networks have not yet generated significant revenue. Most efforts to design a business model for monetizing social networks, are based on contextual display advertising. Another way to monetize social networks is viral marketing, or advertising through word-of-mouth.
Clearly this needs to be modeled. In this project we will consider several models of how users on a social network behave. This project will use models, probability, game theory, algorithms, and real data.
Van der Waerden Games
Mentor: William Gasarch
The following is a well known: For all 2-colorings of {1,2,3,4,5,6,7,8,9} there exists an equally spaced sequence of length 3 (e.g., 2,5,8) that is all the same color.
One can view this as game: If two players RED and BLUE take turns coloring the numbers in {1,2,3,4,5,6,7,8,9} and the first player to create an equally spaced sequence in her color wins. The above theorem says that the game cannot be a tie. Standard techniques yield that the player who goes first wins.
What if we only color {1,2,3,4,5,6,7,8} and both players play perfectly. Does the first player still win? (This can be worked out- YES.)
The theorem above is a special case of van der Waerden's theorem. We will investiage games based on versions of van der Waerden's theorem. In particular we will write programs that use AI techniques to try to win these games. We may (as happened in summer 2014 with Ramsey Games) find and prove some exact cutoffs as to when a game is a player I win. For more on VDW's theorem and the game see here.
Finding Light Approximate Shortest Path Trees
Mentor: Samir Khuller
While we understand the concept of shortest paths and minimum spanning trees very well, our goal is to study this tradeoff further. In particular are there trees that have good properties of both?
This problem has been widely studied in undirected graphs for decades. In this project we hope to explore some open questions in the context of directed graphs.
Group Key Distribution for Cryptography
Mentor: Jonathan Katz
A Group Key Distibution Scheme allows a sender to share keys with a set of receivers, such that the sender can subsequently send an encrypted message to any desired subset of the receivers. The goal is to do this while minimizing the number of keys each receiver has to store, as well as the size of the encrypted message. Such schemes are used, among other things, to distribute encrypted cable TV or streaming content to (only!) paying subscribers.
In this project, we will investigate the case where there are multiple senders, or even when everyone is both a sender and a receiver! Blending cryptography and combinatorics, the goal will be to develop improved schemes, or to prove lower bounds on efficiency in this setting.
For more information on this topic see the following two papers: here and here.
Students
Burcu Canakci (Univ of Turkey, Unofficial): Using SAT Solverst to Find Ramsey-like Numbers.
Karina Chang (Blair HS): Coopersmiths Algorithm
Megan Chao (MIT):
Albert Cheu (NYU): Van Der Waerden Games
Hannah Christenson (Pomona): Using SAT Solverst to Find Ramsey-like Numbers.
Jeremy Du (Blair HS): Coloring the Plane
Ben Eggers (Univ of Washington)
Robert Fleishman (Blair HS, Unofficial): Using SAT Solverst to Find Ramsey-like Numbers.
Racheal Folowoshele (Rolins College): Probability
Cody Freitag (Univ of Texas at Austin): Group Key Distribution for Cryptography
Kyle Haptonstall (Monmouth College): Can't Stop Game.
Ethan Holland (Blair HS): Coloring the Plane
Alejandro Huerta (Univ of Texas-Pan America): Can't Stop Game
Nathan Klein (Oberlin): Group Key Distribution for Cryptography
Lucianna Kiffer (Tulane): Van Der Waerden Games.
Noah Levine (Blair HS): Coopersmiths Algorithm
Eric Lu (Blair HS, Unofficial)
Geoffrey Martin-Noble (Haverford.edu): Social Networks
Nichole McNabb (Swarthmore): Using SAT Solverst to Find Ramsey-like Numbers.
Naveen Raman (Blair HS): The Exact Change Problem
Murray Riley (Berkeley)
Jordan Schneider (Blair HS): Coopersmiths Algorithm
Katherin Scola (Univ of Rutgers at Camden)
Daniel Smolyak (Robert Montgomery HS, Unofficial): Using SAT solvers to Find Ramsey-like Numbers.
Eyob Tsegaye (Blair HS): Coloring the Plane
Colin Weinshenker (William and Mary): Using Rainbow Tables to Crack Passwords.
Duncan Wilson (University of Nevada): Social Networks
|