- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

At the intersection of computability and algebraic geometry, the

following question arises: does an integral polynomial system of

equations have any integral solutions? Famously, the combined work of

Robinson, Davis, Putnam, and Matiyasevich answers this in the negative.

Nonetheless, algorithms have played in increasing role in the

development of algebraic geometry and its many applications. I address

some research related to this general theme and some outstanding

questions.

following question arises: does an integral polynomial system of

equations have any integral solutions? Famously, the combined work of

Robinson, Davis, Putnam, and Matiyasevich answers this in the negative.

Nonetheless, algorithms have played in increasing role in the

development of algebraic geometry and its many applications. I address

some research related to this general theme and some outstanding

questions.

Series: ACO Student Seminar

The Jacobian (or sandpile group) of a graph is a well-studied group associated with the graph, known to biject with the set of spanning trees of the graph via a number of classical combinatorial mappings. The algebraic definition of a Jacobian extends to regular matroids, but without the notion of vertices, many such combinatorial bijections fail to generalize. In this talk, I will discuss how orientations provide a way to overcome such obstacle. We give a novel, effectively computable bijection scheme between the Jacobian and the set of bases of a regular matroid, in which polyhedral geometry plays an important role; along the way we also obtain new enumerative results related to the Tutte polynomial. This is joint work with Spencer Backman and Matt Baker.

Series: ACO Student Seminar

We study the cost function for hierarchical clusterings introduced by Dasgupta where hierarchies are treated as first-class objects rather than deriving their cost from projections into flat clusters. It was also shown that a top-down algorithm returns a hierarchical clustering of cost at most O (α_n log n) times the cost of the optimal hierarchical clustering, where α_n is the approximation ratio of the Sparsest Cut subroutine used. Thus using the best known approximation algorithm for Sparsest Cut due to Arora-Rao-Vazirani, the top down algorithm returns a hierarchical clustering of cost at most O(log^{3/2} n) times the cost of the optimal solution. We improve this by giving an O(log n)- approximation algorithm for this problem. Our main technical ingredients are a combinatorial characterization of ultrametrics induced by this cost function, deriving an Integer Linear Programming (ILP) formulation for this family of ultrametrics, and showing how to iteratively round an LP relaxation of this formulation by using the idea of sphere growing which has been extensively used in the context of graph partitioning. We also prove that our algorithm returns an O(log n)-approximate hierarchical clustering for a generalization of this cost function also studied in Dasgupta. This joint work with Sebastian Pokutta is to appear in NIPS 2016 (oral presentation).

Series: ACO Student Seminar

We consider the problem

of estimating the mean and covariance of a distribution from iid samples

in R^n in the presence of an η fraction of malicious noise; this is in

contrast to much recent work where the noise

itself is assumed to be from a distribution of known type. This agnostic

learning problem includes many interesting special cases, e.g.,

learning the parameters of a single Gaussian (or finding the best-fit

Gaussian) when η fraction of data is adversarially

corrupted, agnostically learning a mixture of Gaussians, agnostic ICA,

etc. We present polynomial-time algorithms to estimate the mean and

covariance with error guarantees in terms of information-theoretic lower

bounds. We also give an agnostic algorithm for

estimating the 2-norm of the covariance matrix of a Gaussian. This joint

work with Santosh Vempala and Anup Rao appeared in FOCS 2016.

of estimating the mean and covariance of a distribution from iid samples

in R^n in the presence of an η fraction of malicious noise; this is in

contrast to much recent work where the noise

itself is assumed to be from a distribution of known type. This agnostic

learning problem includes many interesting special cases, e.g.,

learning the parameters of a single Gaussian (or finding the best-fit

Gaussian) when η fraction of data is adversarially

corrupted, agnostically learning a mixture of Gaussians, agnostic ICA,

etc. We present polynomial-time algorithms to estimate the mean and

covariance with error guarantees in terms of information-theoretic lower

bounds. We also give an agnostic algorithm for

estimating the 2-norm of the covariance matrix of a Gaussian. This joint

work with Santosh Vempala and Anup Rao appeared in FOCS 2016.

Series: ACO Student Seminar

Graded posets are partially ordered sets equipped with a unique rank

function that respects the partial order and such that neighboring

elements in the Hasse diagram have ranks that differ by one. We

frequently find them throughout combinatorics, including the canonical

partial order on Young diagrams and plane partitions, where their

respective rank functions are the area and volume under the

configuration. We ask when it is possible to efficiently sample elements

with a fixed rank in a graded poset. We show that for certain classes

of posets, a biased Markov chain that connects elements in the Hasse

diagram allows us to approximately generate samples from any fixed rank

in expected polynomial time. While varying a bias parameter to increase

the likelihood of a sample of a desired size is common in statistical

physics, one typically needs properties such as log-concavity in the

number of elements of each size to generate desired samples with

sufficiently high probability. Here we do not even require unimodality

in order to guarantee that the algorithm succeeds in generating samples

of the desired rank efficiently. This joint work with Prateek Bhakta,

Ben Cousins, and Dana Randall will appear at SODA 2017.

function that respects the partial order and such that neighboring

elements in the Hasse diagram have ranks that differ by one. We

frequently find them throughout combinatorics, including the canonical

partial order on Young diagrams and plane partitions, where their

respective rank functions are the area and volume under the

configuration. We ask when it is possible to efficiently sample elements

with a fixed rank in a graded poset. We show that for certain classes

of posets, a biased Markov chain that connects elements in the Hasse

diagram allows us to approximately generate samples from any fixed rank

in expected polynomial time. While varying a bias parameter to increase

the likelihood of a sample of a desired size is common in statistical

physics, one typically needs properties such as log-concavity in the

number of elements of each size to generate desired samples with

sufficiently high probability. Here we do not even require unimodality

in order to guarantee that the algorithm succeeds in generating samples

of the desired rank efficiently. This joint work with Prateek Bhakta,

Ben Cousins, and Dana Randall will appear at SODA 2017.

Series: ACO Student Seminar

Parallel algorithms study ways of speeding up sequential algorithms by

splitting work onto multiple processors. Theoretical studies of parallel

algorithms often focus on performing a small number of operations, but

assume more generous models of communication.

splitting work onto multiple processors. Theoretical studies of parallel

algorithms often focus on performing a small number of operations, but

assume more generous models of communication.

Recent progresses led to parallel algorithms for many graph optimization

problems that have proven to be difficult to parallelize. In this talk I

will survey routines at the core of these results: low diameter

decompositions, random sampling, and iterative methods.

Series: ACO Student Seminar

I will present work on a new application of Markov chains to distributed

computing. Motivated by programmable matter and the behavior of

biological distributed systems such as ant colonies, the geometric

amoebot model abstracts these processes as self-organizing particle

systems where particles with limited computational power move on the

triangular lattice. Previous algorithms developed in this setting have

relied heavily on leader election, tree structures that are not robust

to failures, and persistent memory. We developed a distributed algorithm

for the compression problem, where all particles want to gather

together as tightly as possible, that is based on a Markov chain and is

simple, robust, and oblivious. Tools from Markov chain analysis enable

rigorous proofs about its behavior, and we show compression will occur

with high probability. This joint work with Joshua J. Daymude, Dana

Randall, and Andrea Richa appeared at PODC 2016. I will also present

some more recent extensions of this approach to other problems, which is

joint work with Marta Andres Arroyo as well.

computing. Motivated by programmable matter and the behavior of

biological distributed systems such as ant colonies, the geometric

amoebot model abstracts these processes as self-organizing particle

systems where particles with limited computational power move on the

triangular lattice. Previous algorithms developed in this setting have

relied heavily on leader election, tree structures that are not robust

to failures, and persistent memory. We developed a distributed algorithm

for the compression problem, where all particles want to gather

together as tightly as possible, that is based on a Markov chain and is

simple, robust, and oblivious. Tools from Markov chain analysis enable

rigorous proofs about its behavior, and we show compression will occur

with high probability. This joint work with Joshua J. Daymude, Dana

Randall, and Andrea Richa appeared at PODC 2016. I will also present

some more recent extensions of this approach to other problems, which is

joint work with Marta Andres Arroyo as well.

Series: ACO Student Seminar

We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a $(1 \pm \epsilon)$-spectral sparsifier with amortized update time $poly(\log{n},\epsilon^{-1})$. Second, we give a fully dynamic algorithm for maintaining a $(1 \pm \epsilon)$-cut sparsifier with worst-case update time $poly(\log{n},\epsilon^{-1})$. Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a $(1 + \epsilon)$-approximate minimum cut in an unweighted, undirected, bipartite graph with amortized update time $poly(\log{n},\epsilon^{-1})$.Joint work with Ittai Abraham, Ioannis Koutis, Sebastian Krinninger, and Richard Peng

Series: ACO Student Seminar

We examine a variant of the knapsack problem in which item sizes are

random according to an arbitrary but known distribution. In each

iteration, an item size is realized once the decision maker chooses and

attempts to insert an item. With the aim of maximizing the expected

profit, the process ends when either all items are successfully inserted

or a failed insertion occurs. We investigate the strength of a

particular dynamic programming based LP bound by examining its gap with

the optimal adaptive policy. Our new relaxation is based on a quadratic

value function approximation which introduces the notion of diminishing

returns by encoding interactions between remaining items. We compare the

bound to previous bounds in literature, including the best known

pseudopolynomial bound, and contrast their corresponding policies with

two natural greedy policies. Our main conclusion is that the quadratic

bound is theoretically more efficient than the pseudopolyomial bound yet

empirically comparable to it in both value and running time.

random according to an arbitrary but known distribution. In each

iteration, an item size is realized once the decision maker chooses and

attempts to insert an item. With the aim of maximizing the expected

profit, the process ends when either all items are successfully inserted

or a failed insertion occurs. We investigate the strength of a

particular dynamic programming based LP bound by examining its gap with

the optimal adaptive policy. Our new relaxation is based on a quadratic

value function approximation which introduces the notion of diminishing

returns by encoding interactions between remaining items. We compare the

bound to previous bounds in literature, including the best known

pseudopolynomial bound, and contrast their corresponding policies with

two natural greedy policies. Our main conclusion is that the quadratic

bound is theoretically more efficient than the pseudopolyomial bound yet

empirically comparable to it in both value and running time.

Series: ACO Student Seminar

Motivated by neurally feasible computation, we study Boolean functions

of an arbitrary number of input variables that can be realized by

recursively applying a small set of functions with a constant number of

inputs each. This restricted type of construction is neurally feasible

since it uses little global coordination or control. Valiant’s

construction of a majority function can be realized in this manner and,

as we show, can be generalized to any uniform threshold function. We

study the rate of convergence, finding that while linear convergence to

the correct function can be achieved for any threshold using a fixed set

of primitives, for quadratic convergence, the size of the primitives

must grow as the threshold approaches 0 or 1. We also study finite

realizations of this process, and show that the constructions realized

are accurate outside a small interval near the target threshold, where

the size of the construction at each level grows as the inverse square

of the interval width. This phenomenon, that errors are higher closer to

thresholds (and thresholds closer to the boundary are harder to

represent), is also a well-known cognitive finding. Finally, we give a

neurally feasible algorithm that uses recursive constructions to learn

threshold functions. This is joint work with Christos Papadimitriou and

Santosh Vempala.

of an arbitrary number of input variables that can be realized by

recursively applying a small set of functions with a constant number of

inputs each. This restricted type of construction is neurally feasible

since it uses little global coordination or control. Valiant’s

construction of a majority function can be realized in this manner and,

as we show, can be generalized to any uniform threshold function. We

study the rate of convergence, finding that while linear convergence to

the correct function can be achieved for any threshold using a fixed set

of primitives, for quadratic convergence, the size of the primitives

must grow as the threshold approaches 0 or 1. We also study finite

realizations of this process, and show that the constructions realized

are accurate outside a small interval near the target threshold, where

the size of the construction at each level grows as the inverse square

of the interval width. This phenomenon, that errors are higher closer to

thresholds (and thresholds closer to the boundary are harder to

represent), is also a well-known cognitive finding. Finally, we give a

neurally feasible algorithm that uses recursive constructions to learn

threshold functions. This is joint work with Christos Papadimitriou and

Santosh Vempala.