ARC student wins First Place UROC Award
James Robinson (Mentor: Santosh Vempala) has won First Place Prize ($750) in this year's UROC Symposium for "MANET Routing: Using Manifolds and the WDL". See complete UROC results.
Student Fellowships Awarded for Summer 2008
Santosh Vempala reports that the ARC committee (Profs. Cook, Tetali and Vigoda) has selected the following 4 projects for 1/2 funding this summer (listed in alphabetical order). Congratulations to all 4 winners!
Georgios Amanatidis, Math (mentor Milena Mihail):
Models for Routing and Social Complex Networks
Deeparnab Chakrabarty, CS (mentor Vijay Vazirani):
Budget-Constrained Auctions
Sam Greenberg, Math (mentor Dana Randall):
Random Sampling via Geometric Coupling
Kael Stilp, ISYE (mentor Ozlem Ergun)
Searching for the Core with Column Generation
Computing Assistant Professors Nick Feamster and Adam Kalai Win Sloan Fellowships
Two School of Computer Science faculty members, Nick Feamster in the Networking and Telecommunications Group and GTISC, and Adam Kalai in the Theory Group and ARC ThinkTank, have been awarded the prestigious Alfred P. Sloan fellowships for 2008. Sloan Research Fellowships are awarded by the Alfred P. Sloan Foundation to encourage the work of the very best young faculty members in diverse fields such as Computer Science, Mathematics, Physics, Chemistry, Molecular Biology, Economics, and Neuroscience. The awardees are chosen on the basis of their prior research accomplishments and outstanding promise of making fundamental contributions to their research areas. Thirty-five Sloan Fellows have won Nobel Prizes later in their careers.
Two areas in which Dr. Kalai has made strong contributions are online algorithms and machine learning. In online algorithms, he has contributed a new proof of a stock market strategy called the Universal Portfolio which has led to a polytime algorithm using a biased random walk - a new tool for online algorithms. In the past few years, Adam’s work on the online decision problem has changed the course of the field. Adam discovered an algorithm for the general problem of online linear optimization where costs add up over the sequence: maintain the best solution on the past, on a randomly perturbed version of the data so far. Adam’s proof is so transparent that it has lead to many follow-up papers in a short time. In learning theory, he found a new algorithm for learning parity functions in the presence of random noise. This settles a theoretical question about the power of statistical learning and remains the best-known algorithm for this central problem in learning theory. His algorithm also has a direct application to the classic question of finding the shortest vector in a lattice.
Dr. Feamster’s research agenda is in the area of network operations. He interprets the scope of this research to encompass questions regarding network connectivity such as how to make it robust and how to incentivize it within the context of Internet economics. His research also considers network security as an operational primitive and is concerned with how network monitoring can be used to enhance security. Within these broad research areas, Nick has several important and highly creative research contributions including work on a routing configuration compiler that incorporates program analysis techniques to analyze complex router configurations in a network to predict their behavior; a technique for detecting spam through network traffic monitoring that relies on understanding the network-level behavior of spam and using that signature to detect spam as it is being carried over the network; and an architecture for network virtualization that can provide robust and flexible network connectivity, an idea first proposed by Dr. Feamster as the basis of a future Internet design.
Assistant professors Feamster and Kalai are among the 16 recipients of the award for Computer Science this year. The award carries a two-year, $50,000 grant for the faculty to spend on their respective research interests. Previous recipients of the fellowship at the College of Computing include distinguished professor Santosh Vempala, assistant professor Subhash Khot, associate professor Beth Mynatt, and associate professor Dana Randall.
About Nick Feamster: www.cc.gatech.edu/directory/nick-feamster
About Adam Kalai: www.cc.gatech.edu/directory/adam-kalai
About Sloan Fellowships: www.sloan.org/programs/scitech_fellowships.shtml
List of this year's awardees: www.sloan.org/programs/fellowshiplist.shtml
ARC ThinkTank Faculty Present Ideas to Improve the Internet and Speed-Up Wireless Networks at HotNets 2007
Papers by Algorithms and Randomness Center (ARC) and ThinkTank members that provide new ways of increasing Internet connectivity and the speed of wireless networks will be presented at the Sixth Workshop on Hot Topics in Networks (HotNets-VI) from November 14-15 in Atlanta, GA.
A paper titled "Path Splicing: Reliable Connectivity with Rapid Recovery," provides a method to radically improve availability on the Internet. Co-authored by College of Computing graduate student Murtaza Motiwala, College of Computing Assistant Professor Nick Feamster, and College of Computing Professor and ARC ThinkTank Director Santosh Vempala, it shows how a simple extension of standard Internet routing algorithms will create networks that can handle more failures, leading to exponentially higher reliability for Internet users.
A second paper provides an algorithm for better wireless network routing, which can be implemented on commonly available platforms. "Life (and routing) on the Wireless Manifold," co-authored by College of Computing graduate student Varun Kanade and Santosh Vempala, shows how wireless signal propagation can be viewed as travel along shortest paths on a distorted surface. They give an algorithm for constructing such a manifold from signal decay measurements, leading to efficient representations and routing algorithms for mobile networks. They plan to evaluate and refine the algorithms jointly with College of Computing Assistant Professor Mike Best and the TeNet group in Chennai, India.
The Sixth Workshop on Hot Topics in Networks (HotNets-VI) will bring together researchers in the networking systems community to engage in lively discussion of future trends in networking research and technology. The workshop provides a venue for researchers to present and discuss ideas that have the potential to significantly influence the community in the long term; the goal is to promote community-wide discussions of those ideas.
ARC ThinkTank Member Wins Johnson Prize for Work on Ancient Math Problem
College of Computing Postdoctoral Fellow and ARC ThinkTank member Luis Rademacher has won the Johnson prize for 2006-07, given by the MIT mathematics department to the most outstanding paper co-authored by a graduate student.
Rademacher's paper, titled "Dispersion of Mass and the Complexity of Randomized Geometric Algorithms," deals with computing the volume of a convex body--an ancient mathematical problem studied by Euclid, Kepler and Minkowski, among others. The paper was a collaboration with his advisor, College of Computing Professor and ARC ThinkTank Director Santosh Vempala. The paper appeared last year in the IEEE Symposium on the Foundations of Computer Science.
In his work, Rademacher proves a nearly quadratic lower bound on the complexity of any randomized algorithm that approximates the volume of a convex body in R^n. The lower bound complements progress over the past two decades on efficient algorithms for volume computation. It does so using deep new connections between convex geometric analysis and algorithmic complexity.
GTISC and ARC Researchers Collaborate to Develop Next-Generation Spam Filters
Graduate student Anirudh Ramachandran's work on filtering spam using network-level properties will appear at the ACM Conference on Computer and Communications Security (CCS), ACM's top security conference, at the end of October. Ramachandran and his advisor, Assistant Professor Nick Feamster, have been working with Professor Santosh Vempala to develop next-generation spam filtering techniques.
Spam is becoming increasingly virulent as it makes use of images and PDFs to evade content-based filters. To make matters worse, spammers are sending spam from "fresh" machines every day, which makes it difficult to maintain static blacklists of known bad senders.
To get a step ahead, the researchers have taken a different approach: rather than filtering spam based on
content or an ephemeral identity of the sender (e.g., an IP address), the researchers have invented a new
technique called "behavioral blacklisting". Behavioral blacklisting aims to learn and "fingerprint" spammers' sending patterns---for example, the set of recipients a particular sender is targeting---and blacklist senders based on their sending behavior, rather than a fixed identity.
The researchers developed their first behavioral blacklisting technique by applying Professor Vempala's novel spectral clustering algorithms, which have also successfully been applied to other areas (e.g., Web search). You can read the paper here (PDF).
ARC ThinkTank Makes Strong Contribution at Top ACM Symposium
(July 20, 2007) - Five papers from members of the Algorithms and Randomness Center and ThinkTank (ARC ThinkTank) were presented at the Symposium on the Theory of Computing (STOC 2007), June 10-13 in San Diego, California. The symposium is sponsored by the Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory (SIGACT) and is one of the top annual conferences in theoretical computer science.
ARC ThinkTank brings together faculty from the College of Computing at Georgia Tech, along with the Schools of Math and Industrial Systems and Engineering (ISyE) to find algorithms and algorithmic models for real-world problems across the sciences and, in the process, seeking new directions and techniques for the emerging theory of algorithms.
The following papers were presented and and can be downloaded by ACM subscribers:
"Playing Games with Approximation Algorithms" - co-authored by Adam Kalai, assistant professor
"Combinatorial Complexity in O-minimal Geometry" - by Saugata Basu, associate professor joint with the School of Mathematics
"Randomly Coloring Planar Graphs with Fewer Colors than the Maximum Degree" - co-authored by Eric Vigoda, associate professor and Juan Vera, post-doc
"Eisenberg-Gale Markets: Algorithms and Structural Properties" - co-authored by Vijay Vazirani, professor and former student Kamal Jain, Microsoft Research
"Simple Deterministic Approximation Algorithms for Counting Matchings" - co-authored by Prasad Tetali, professor joint with the School of Mathematics
The ARC ThinkTank brings together faculty from the College of Computing at Georgia Tech, along with the Schools of Math and Industrial Systems and Engineering (ISyE) to find algorithms and algorithmic models for real-world problems across the sciences and, in the process, seeking new directions and techniques for the emerging theory of algorithms.
More information on STOC '07 can be found at the symposium website.
ARC ThinkTank Offers Resources to Campus Researchers
A recent article in The Whistle Georgia Tech Faculty/Staff Newspaper announced the launch of the Algorithms and Randomness Center ThinkTank. View the entire article here.
ARC ThinkTank Faculty Present Theoretical Advances
Members of the Algorithms & Randomness Center and ThinkTank (ARC ThinkTank) recently presented theoretical advances at IEEE sponsored Symposium on Foundations of Computer Science (FOCS) in Berkeley, CA. ARC ThinkTank brings together faculty from the College of Computing at Georgia Tech, along with Math and ISyE to find algorithms and algorithmic models for real-world problems across the sciences and, in the process, seeking new directions and techniques for the emerging theory of algorithms. View the entire article here.