Fellowships

Spring 2013

The purpose of this project is to provide new models and algorithms for image processing. We consider the case of reconstructing noisy and blurred images, by optimization models that combine data fitting with a regularization term.

Nash-Williams conjectured in the 1960’s that given an infinite sequence of finite graphs, one graph in the sequence admits a weak (strong, respectively) immersion of a graph in the sequence of smaller index.

The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the classical work of Garey and Johnson(1979).

Fall 2012

Consider the problem of coloring a 3-colorable graph using as few colors as possible. In the regime of polynomial time approximation algorithms, this problem has been studied extensively.

Fall 2012

We propose to investigate generating truly random bases for regular matroids (or totally unimodular matrices). For the general case of regular matroids the only known technique, due to Dyer and Frieze, is to start with an arbitrary basis and to perform a random walk on the "graph of bases".

Spring 2011

Pseudorandom generators and pseudorandom functions have been widely studied and have a lot of uses in cryptography.

Spring 2011

The hard-core model in a graph G, is a parametric measure of the independent sets of the graph in which the 'fugacity' parameter favors greater independent sets as it increases.

Spring 2011

This research project studies the hard-core model (also known as the weighted independent set model) on the square lattice Z^2. For a (finite) graph G = (V, E), the hard-core model is defined on the set Omega of independent sets of G.

Fall 2011

We consider sampling weighted permutations of the integers [1,...,n] with a preference towards permutations that are "more sorted."

Fall 2011

The Integer Programming Problem is stated as follows: given a system of linear inequalities...

Fall 2011

The central goal of the proposed research is to \thresholdize" the most important operations in lattice-based cryptography.

Fall 2011

One way to explore a broad terrain such as a polar ice cap, the surface of Mars, or the bottom of the ocean is to use a network of small robots.

Fall 2011

The goal of our research is to obtain efficient implementations of first-order algorithms for solving (1), including instances that may not be SDPs, with the same approach of specializing a variant of the HPE methods as described above.

Fall 2011

This work is concerned with approximating CSPs with additional cardinality constraints on the assignment.

Fall 2011

In this project we will study two problems that fall in the general realm of allocation problems for which the known optimal algorithms have large polynomial running time.

Spring 2010

Da Kuang (Haesun Park) - Nonnegative matrix factorization (NMF), when applied to clustering high-dimensional data, can achieve much higher accuracy than traditional K-means, especially using the alternating-nonnegativity-least-squares algorithm (ANLS).

Spring 2010

Ravi Sastry (Mentor Alexander G. Gray) - Local kernel machines work by finding locally linear decision surfaces in the input space. They are built upon the fact that any differentiable function can be locally expressed as a linear function up to a small remainder.

Spring 2010

Our objective is to study the possibility of improvements at either the lower or the upper bounds.

Spring 2010

Xuefeng GAO (ISYE) (Prof Ton Dieker (ISYE). The objective of the proposed research is to develop methods to do capacity optimization in a large feedforward queueing network.

Fall 2010

It is noticeable that among Karp's 21 NP-complete problems, the integer programming problem is one that lacks understanding under the probabilistic input setting.

Fall 2010

Price bubbles, crashes, and cycles have occurred repeatedly over the past four centuries, and have been described and studied in many ways.

Fall 2010

Qie He, ISYE, (mentors: Shabbir Ahmed; George Nemhauser, ISYE) - We are interested in the stochastic integer programming (SIP) model that captures the uncertainty in real-world problems.

Fall 2010

The project makes an attempt to answer some open questions related to the binary classification problem in the active learning framework.

Fall 2010

We propose to investigate a graph-theoretic analogue of Torelli's theorem, which is the assertion in classical algebraic geometry that an algebraic curve is determined, up to isomorphism, by its principally polarized Jacobian.

Fall 2010

We are interested in applying tensors and spectral techniques to the study of random constraint satisfaction problems.

Spring 2009

This project deals with the problem of circular security, an issue that arises in several contexts, including distributed systems with complicated key management schemes.

Spring 2009

Andrea Montanari, Ricardo Restrepo, Prasad Tetali - Random instances of Constraint Satisfaction Problems (CSP's) appear to be hard for all known algorithms, when the number of constraints per variable lies in a certain interval.

Spring 2009

I am working on efficient approaches to perform several independent random walks, in the graph streaming model (important for database and data mining communities) and the distributed computing model (important for peer to peer networks).

Fall 2009

Daniel Dadush, ISYE (Mentor Santosh Vempala) - Towards the KLS Conjecture for Convex Bodies: Motivated by applications to Volume Computation and Algorithmic Sampling, in 97' Kannan, Lovasz, and Simonovits posed a conjecture that has become a central problem in convex geometry.

Fall 2009

Atish Das Sarma, CS (Mentor Richard J. Lipton) - In this work, we focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample.

Fall 2009

Luyi Gui (ISYE) (Ozlem Ergun), We study a stochastic multicommodity network where the edge capacity and commodity demand are privately owned by network users and their levels are subject to random variations.

Fall 2009

Colloids are mixtures of molecules that separate because molecules have a tendency to adhere to other molecules of the same type. Physicists have introduced various hard-core models that are believed to demonstrate how this can be caused by purely entropic effects.

Map of Georgia Tech

Georgia Tech Algorithm and Randomness Center
266 Ferst Drive NW
Atlanta, GA 30332-0765
Phone: 404-385-3190