All Seminars
| 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-01-29 at 3:00PM |
| Venue: MSC W201 |
| 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: Something special... |
|---|
| Seminar: Algebra |
| Speaker: Ken Ono of Emory |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2014-01-28 at 3:00PM |
| Venue: W304 |
| Download Flyer |
| Abstract: |
| Title: More examples of non-rational adjoint groups |
|---|
| Seminar: Algebra |
| Speaker: Nivedita Bhaskhar of Emory University |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2014-01-21 at 4:00PM |
| Venue: W302 |
| Download Flyer |
| Abstract: A k-variety is said to be rational if its function field is purely transcendental over k. The first example of a non-rational adjoint k-group PSO(q) was given by Merkurjev as a consequence of his computations of R-equivalence classes of adjoint classical groups. The quadratic form in question has non-trivial discriminant which property is used crucially in the proof. Gille provided the first example of a quadratic form of trivial discriminant whose associated adjoint group is non-rational. In this talk we give a recursive construction to produce examples of $k_n$-quadratic forms $q_n$ in the n-th power of the fundamental ideal in the Witt ring whose corresponding adjoint groups PSO($q_n$) are not (stably) rational. |
| Title: Hierarchy and Structure: Nonparametric models for space, language, and relations |
|---|
| Seminar: Computer Science |
| Speaker: Alex Smola of Google/CMU |
| Contact: Eugene Agichtein, eugene@emory.edu |
| Date: 2014-01-09 at 3:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Latent variable models are a powerful tool for analyzing structured data. They are well suited to capture documents, location and preference information. That said, often a simple hierarchical model is insufficient for modeling observations since real data tends to be more nuanced in some aspects rather than others. In other words, descriptions work best if they allow for variable depth and refined descriptions. Models such as the nested Chinese Restaurant Franchise address these issues. I will present examples of their application to location inference for Twitter and structured recommender systems. |
| Title: Computational Methods for Centrality Measurements in Complex Networks |
|---|
| Defense: Dissertation |
| Speaker: Christine Klymko of Emory University |
| Contact: Christine Klymko, cklymko@emory.edu |
| Date: 2013-12-10 at 3:30PM |
| Venue: W302 |
| Download Flyer |
| Abstract: |
| Title: Scalable and Privacy-Preserving Searchable Cloud Data Services |
|---|
| Seminar: Computer Science |
| Speaker: Ming Li of Utah State University |
| Contact: Li Xiong, lxiong@mathcs.emory.edu |
| Date: 2013-12-09 at 4:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Cloud computing is envisioned as the next generation architecture of IT enterprises, which provides convenient remote access to massively scalable data storage and application services. Despite the cloud’s promise for huge potential economical savings, its benefits may not be fully realized, due to wide public concerns that users’ private data may be involuntarily exposed to or mishandled by the cloud providers. Although end-to-end encryption has been proposed as a promising solution for secure cloud data storage, how to effectively support flexible data utilization such as searches over encrypted cloud data becomes a primary challenge, which is the key toward building full-fledged privacy-assured cloud data storage. In this talk, I will first identify the system requirements and challenges in privacy-preserving searchable outsourced cloud data services, that is to simultaneously achieve privacy assurance (data and query confidentiality), practical efficiency (scalable with large volumes of data), and high usability (flexible query functionalities). Among these goals, privacy and the other two are often in conflict with each other and our research aims at finding a better tradeoff. As an example, I will present our recent work on privacy-preserving multi-keyword ranked search supporting similarity-based ranking. The proposed approach integrates novel cryptographic primitives with information-retrieval principles and efficient data structures. A “best-effort” privacy model is adopted while much faster-than-linear search time is achieved in an empirical sense. Finally, I will outline some future challenges that need to be resolved to make privacy-preserving searchable cloud data service a reality.\\ \\ Bio:\\ Ming Li is an Assistant Professor in the Computer Science Department at Utah State University. He received his Ph.D. in Electrical and Computer Engineering from Worcester Polytechnic Institute in 2011. His current main research interest is cyber security and privacy, with emphases on security and privacy in cloud computing and big data, security in wireless networks and cyber-physical systems. |
| Title: On Erdos' conjecture on the number of edges in 5-cycles |
|---|
| Seminar: Combinatorics |
| Speaker: Zoltan Furedi of Renyi Institute of Mathematics, Budapest, Hungary |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2013-12-06 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: Erdos, Faudree, and Rousseau (1992) showed that a graph on n vertices and at least $[n^2/4]+1$ edges has at least $2[n/2]+1$ edges on triangles and this result is sharp. They also considered a conjecture of Erdos that such a graph can have at most $n^2/36$ non-pentagonal edges with an extremal graph having two components, a complete graph on $[2n/3]+1$ vertices and a complete bipartite graph on the rest. This was mentioned in other papers of Erdos and also it is No. 27 in Fan Chung's problem book.\\ \\ In this talk we give a graph of $[n^2/4]+1$ edges with much more, namely $n^2/8(2+\sqrt{2})$ + $O(n) = n^2/27.31…$ pentagonal edges, disproving the original conjecture. We show that this coefficient is asymptotically the best possible.\\ \\ Given graphs H and F let $E_0(H,F)$ denote the set of edges of H which do not appear in a subgraph isomorphic to F, and let $h(n,e,F)$ denote the maximum of $|E_0(H,F)|$ among all graphs H of n vertices and e edges. We asymptotically determine $h(n,cn^2, C_3)$ and $h(n,cn^2, C_5)$ for fixed c, $1/4 < c < 1/2$. For $2k+1\ge$ 7 we establish the conjecture of Erdos et al. that $h(n,cn^2, C_{2k+1})$ is obtained from the above two-component example.\\ \\ One of our main tools (beside Szemeredi's regularity) is a new version of Zykov's symmetrization what we can apply for more graphs, simultaneously. |
| Title: Degree 3 cohomological invariants and quadratic splitting of hermitian forms |
|---|
| Seminar: Algebra |
| Speaker: Jean-Pierre Tignol of Université Catholique de Louvain |
| Contact: David Zureick-Brown, dzb@mathcs.emory.edu |
| Date: 2013-11-26 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: Using variations on the Rost invariant of Spin groups, we define an invariant with values in $H^3(F,\mu_2)$ for hermitian forms with vanishing lower-degree invariants, and discuss the relation between this invariant and the existence of quadratic extensions of the base field that make the hermitian form split hyperbolic. (Joint work in progress with Anne Qu\'eguiner-Mathieu) |
| Title: 3-Coloring and 3-List-Coloring Graphs on Surfaces |
|---|
| Seminar: Combinatorics |
| Speaker: Luke Postle of Emory University |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2013-11-22 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: Grotzsch proved that every triangle-free planar graph is 3-colorable. This theorem follows easily once one proves that every planar graph of girth at least five is 3-colorable. There are now three short proofs of this using three different methods: discharging, list-coloring, and the new potential technique of Kostochka and Yancey. It is natural to wonder how this can be generalized to surfaces; for example whether locally planar graphs of girth at least five are 3-colorable or whether there exists a polynomial-time algorithm to decide 3-coloring on a fixed surface. Both of these results are implied by the following more general result of Thomassen: For every surface, there exist only finitely many 4-critical graphs of girth at least five embeddable on that surface. Dvorak, Kral and Thomas provided a discharging proof of Thomassen's theorem to prove a stronger result that the number of vertices in such graphs is linear in genus. This was a needed ingredient in their proof of Havel's conjecture which states that a planar graph with triangles far apart is 3-colorable. We will discuss two new proofs of this linear bound result, one using list-coloring and one using the potential technique, and their various corollaries, such as the generalization of Thomassen's theorem to 3-list-coloring. |
| Title: The distribution of 2-Selmer ranks and additive functions |
|---|
| Seminar: Algebra |
| Speaker: Robert Lemke Oliver of Stanford University |
| Contact: TBA |
| Date: 2013-11-21 at 5:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: The problem of determining the distribution of the 2-Selmer ranks of quadratic twists of an elliptic curve has received a great deal of recent attention, both in works conjecturing distributions and in those providing solutions; in both cases, the nature of the two-torsion of the elliptic curve plays a cruical role. In particular, if $E/\mathbb{Q}$ has full two-torsion, the distribution is known, due to work of Heath-Brown, Swinnerton-Dyer, and Kane, and if $E$ possesses no two-torsion, then, again, the distribution is known, due to work of Klagsbrun, Mazur, and Rubin, though with the caveat that one arranges discriminants in a non-standard way. In stark contrast to these two cases, we show that if $K$ is a number field and $E/K$ is an elliptic curve with partial two-torsion, then no limiting distribution on 2-Selmer ranks exists. We do so by showing that, for any fixed integer $r$, at least half of the twists of $E$ have 2-Selmer rank greater than $r$, and we establish an analogous result for simultaneous twists, either for multiple elliptic curves twisted by the same discriminant or for a single elliptic curve twisted by a tuple of discriminants. These results depend upon connecting the 2-Selmer rank of twists to the values of an additive function and then establishing results analogous to the classical Erd\H{o}s-Kac theorem. This work is joint with Zev Klagsbrun. |