All Seminars
| Title: Bounded gaps between primes |
|---|
| Seminar: Joint Athens-Atlanta Number Theory Seminar |
| Speaker: James Maynard of Universite de Montreal |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2014-02-25 at 5:15PM |
| Venue: W302 |
| Download Flyer |
| Abstract: It is believed that there should be infinitely many pairs of primes which differ by 2; this is the famous twin prime conjecture. More generally, it is believed that for every positive integer $m$ there should be infinitely many sets of $m$ primes, with each set contained in an interval of size roughly $m\log{m}$. We will introduce a refinement of the `GPY sieve method' for studying these problems. This refinement will allow us to show (amongst other things) that $\liminf_n(p_{n+m}-p_n)<\infty$ for any integer $m$, and so there are infinitely many bounded length intervals containing $m$ primes. |
| Title: Dynamic Performance Profiling of Data Caches |
|---|
| Colloquium: N/A |
| Speaker: Ymir Vigfusson of Reykjavik University |
| Contact: Vaidy Sunderam, vss@emory.edu |
| Date: 2014-02-24 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Scalable data replication protocols and layers, such as streaming, multicast and caching, enable large data-driven distributed systems to be practical. As a concrete example, large-scale in-memory object caches like memcached are now widely used to accelerate popular web sites and to reduce burden on backend databases. Yet operators still have limited visibility into how these caches should be set up to optimally accommodate the workloads they see. How much would the cache performance improve from additional cache space, or by adding more cache servers to the pool? Since resources come at a cost, to what extent would request latencies deteriorate if cache memory were repurposed for a different service?\\ \\ In this talk, I'll focus on some of the latest research questions pertaining to scalable data replication and large-scale distributed caches. In particular, I'll home in on the challenge of providing online monitoring of the cost and benefits of memory space in a large-scale cache, enabling cache operators to answer the questions above without requiring extraneous trace collection and manual offline tuning. I will introduce general and efficient algorithms for dynamically estimating hit rate curves -- histograms of cache hit rate as a function of memory size -- which can be plugged into cache replacement policies such as LRU.\\ \\ Extensive simulations on cache benchmarks indicate that these methods provide accurate estimates of hit rate at different cache sizes. Experiments on an implementation of these methods in memcached showed that hit rate curves were dynamically estimated at over 98% accuracy with only a small drop in throughput. The results are encouraging and suggest that exposing hit rate curves can be a practical method for improving provisioning and metering of large-scale data caches. |
| Title: Decision Making and Inference under Limited Information and Large Dimensionality |
|---|
| Colloquium: N/A |
| Speaker: Stefano Ermon of Cornell University |
| Contact: Vaidy Sunderam, vss@emory.edu |
| Date: 2014-02-21 at 3:00PM |
| Venue: MSC W201 |
| Download Flyer |
| Abstract: Statistical inference in high-dimensional probabilistic models (i.e., with many variables) is one of the central problems of statistical machine learning and stochastic decision making. To date, only a handful of distinct methods have been developed, most notably (MCMC) sampling, decomposition, and variational methods. In this talk, I will introduce a fundamentally new approach based on random projections and combinatorial optimization. Our approach provides provable guarantees on accuracy, and outperforms traditional methods in a range of domains, in particular those involving combinations of probabilistic and causal dependencies (such as those coming from physical laws) among the variables. This allows for a tighter integration between inductive and deductive reasoning, and offers a range of new modeling opportunities. As an example, I will discuss an application in the emerging field of Computational Sustainability aimed at discovering new fuel-cell materials where we greatly improved the quality of the results by incorporating prior background knowledge of the physics of the system into the model. |
| Title: Harnessing the Power of Crowd for On-Demand Geographical Data Collection |
|---|
| Colloquium: Computer Science |
| Speaker: Cyrus Shahabi of University of Southern California |
| Contact: Li Xiong, lxiong@emory.edu |
| Date: 2014-02-20 at 12:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: GeoCrowd is an online spatial crowdsourcing market (similar to Amazon’s Mechanical Turk) that matches geo tasks (i.e., tasks associated with a specific location and time such as “Take pictures of Tommy Trojan during 2012 USC-UCLA game”) to human workers. Every person with mobile devices can now act as a multi-modal sensor collecting various types of data instantaneously (e.g., picture, video). With GeoCrowd, subscribers can publish tasks with specific space and time attributes. Subsequently, the workers (with GeoCrowd mobile app) can perform the tasks if they are at the right time and at the right place and upload the results to the GeoCrowd server(s). In this talk, I first introduce our generic framework for GeoCrowd and discuss various techniques for optimal assignment of spatiotemporal tasks to human workers. Next, I show how we can extend this framework to incorporate trust in GeoCrowd in order to ensure workers satisfy a confidence value given by the task requester. Finally, I will show an application of the GeoCrowd framework in a commercial domain. |
| Title: Extremal problems on optimizing the number of nonnegative subsets |
|---|
| Colloquium: N/A |
| Speaker: Hao Huang of The Institute for Advanced Study and DIMACS |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2014-02-20 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Extremal combinatorics studies the maximum or minimum possible size of a combinatorial structure satisfying certain properties. It is one of the central themes of modern discrete mathematics, and has numerous natural connections to other areas including probability, number theory and theoretical computer science. As an example, in this talk I will discuss some recent progress on a fifty-year-old conjecture of Erdos on hypergraph matching, and describe its relation with several other extremal problems on optimizing the number of nonnegative. Our work settles conjectures of Manickam, Miklos and Singhi, and of Tsukerman. |
| Title: Applications of Flag Algebras in Hypercubes and Permutations |
|---|
| Colloquium: N/A |
| Speaker: Bernard Lidicky of The University of Illinois at Urbana-Champaign |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2014-02-19 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Flag algebras provide a method, recently developed by Razborov, designed for attacking problems in extremal graph theory. There are recent applications of the method also in discrete geometry or permutation patterns. The aim of talk is to give a gentle introduction to the method and show some of its applications to hypercubes and permutations. The talk is based on joint work with J. Balogh, P. Hu, H. Liu, O. Pikhurko, B. Udvari, and J. Volec. |
| Title: Lifting Tropical Curves and Linear Systems on Graphs |
|---|
| Seminar: Algebra |
| Speaker: Eric Katz of University of Waterloo |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2014-02-18 at 4:00PM |
| Venue: W302 |
| Download Flyer |
| Abstract: Tropicalization is a procedure for associating a polyhedral complex to a subvariety of an algebraic torus. We explain the method of tropicalization and study the question of which graphs arise from tropicalizing algebraic curves. By applying Matthew Baker's technique of specialization of linear systems from curves to graphs, we are able to give a necessary condition for a balanced weighted graph to be the tropicalization of a curve. Our condition is phrased in terms of the harmonic theory of graphs, reproduces the known necessary conditions, and also gives new conditions. Moreover, our method gives a combinatorial way of thinking about the deformation theory of algebraic varieties. |
| Title: Randomized Block Coordinate Gradient Methods for a Class of Structured Nonlinear Programming |
|---|
| Colloquium: N/A |
| Speaker: Zhaosong Lu of Simon Fraser University |
| Contact: James Nagy, nagy@mathcs.emory.edu |
| Date: 2014-02-17 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Nowadays a class of huge-scale structured optimization problems arise in some emerging areas such as machine learning. They can be reformulated as minimizing the sum of a smooth and block separable nonsmooth functions. For these problems, it is prohibitive to evaluate the full gradient of the smooth component of the objective function due to huge dimensionality and hence the usual gradient methods cannot be efficiently applied. Nevertheless, its partial gradients can often be computed much more cheaply. In this talk we study a randomized block coordinate gradient (RBCG) method for solving this class of problems. At each iteration this method randomly picks a block, and solves a proximal gradient subproblem over the subspace defined by the block that only uses a partial gradient and usually has a closed-form solution. We present new iteration complexity results for this method when applied to convex problems. We also propose a nonmonotone RBCG method for solving a class of nonconvex problems with the above structure, and establish their global convergence and iteration complexity. In addition, we present new complexity results for the accelerated RBCG method proposed by Nesterov for solving unconstrained convex optimization problems. Finally, we discuss the application of these methods for solving some support vector machine problems and report some computational results. (This is a joint work with Lin Xiao at Microsoft Research Redmond.) |
| Title: Fast algorithms for electronic structure analysis |
|---|
| Colloquium: N/A |
| Speaker: Lin Lin of Lawrence Berkeley National Laboratory |
| Contact: James Nagy, nagy@mathcs.emory.edu |
| Date: 2014-02-12 at 4:00PM |
| Venue: MSC W303 |
| Download Flyer |
| Abstract: Kohn-Sham density functional theory (KSDFT) is the most widely used electronic structure theory for molecules and condensed matter systems. For a system with N electrons, the standard method for solving KSDFT requires solving N eigenvectors for an $O(N) * O(N)$ Kohn-Sham Hamiltonian matrix. The computational cost for such procedure is expensive and scales as $O(N^3)$. We have developed pole expansion plus selected inversion (PEXSI) method, in which KSDFT is solved by evaluating the selected elements of the inverse of a series of sparse symmetric matrices, and the overall algorithm scales at most $O(N^2)$ for all materials including insulators, semiconductors and metals. The PEXSI method can be used with orthogonal or nonorthogonal basis set, and the physical quantities including electron density, energy, atomic force, density of states, and local density of states are calculated accurately without using the eigenvalues and eigenvectors. The recently developed massively parallel PEXSI method has been implemented in SIESTA, one of the most popular electronic structure software packages using atomic orbital basis sets. The resulting method can allow accurate treatment of electronic structure in a unprecedented scale. We demonstrate the application of the method for solving graphene-like structures with more than 30,000 atoms, and the method can be efficiently parallelized 10,000 - 100,000 processors on Department of Energy (DOE) high performance machines. |
| Title: Canceled due to weather |
|---|
| Seminar: Algebra |
| Speaker: Matt Ballard of University of South Carolina |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2014-02-11 at 4:00PM |
| Venue: W302 |
| Download Flyer |
| Abstract: One of the most basic invariants of an algebra is its global dimension, the maximal $n$ for which $Ext^n_A(M,N)$ does not vanish. For an algebra A of finite global dimension, what are the possible global dimensions of algebras Morita equivalent to A? Derived Morita equivalent to A? I will review these notions, discuss these questions, and then their extensions to differential graded algebras, which will naturally lead into Orlov spectra. |