Georgia Institute of Technology Georgia Tech Algorithm and Randomness Center (ARC)

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.

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.

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".

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

The problem of finding the sparsest cut in graphs is a well known and intensively studied problem.

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.

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.

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

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

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

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.

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.

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

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.

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).

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.

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

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.

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.

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

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.

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

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.

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

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

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.

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).

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.

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.

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.

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.