PACM Colloquium
Spring 2017
PACM Colloquium: Survival and Schooling HydrodynamicsSpeaker: Petros Koumoutsakos, ETH Zürich Date: Feb 13 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: The aqueous environment of natural swimmers mediates magnificent patterns of schooling as well as their escape and attack routines. We study the fluid mechanics of single and multiple swimmers through simulations that rely on state of the art multiresolution vortex methods. Stochastic optimisation and machine learning algorithms are used to find optimal shapes and motions for single and synchronised patterns for multiple swimmers. I will discuss how the orchestration of body deformations and vortex dynamics can result in thrust and energy savings for these artificial swimmers and juxtapose these findings with swimming patterns of natural organisms. Lessons learned can assist the design and operation of energy efficient swimming devices. Petros Koumoutsakos is Full Professor of Computational Science at ETH Zurich since 2000. He received his Diploma (1986) in Naval Architecture at the National Technical University of Athens and a Master’s (1987) at the University of Michigan, Ann Arbor. He received his Master’s (1988) in Aeronautics and his PhD (1992) in Aeronautics and Applied Mathematics from the California Institute of Technology. He is Fellow of the American Society of Mechanical Engineers, the American Physical Society and the Society of Industrial and Applied Mathematics. He is recipient of the ACM Gordon Bell prize in Supercomputing and the Advanced Investigator Award by the European Research Council (2013). He is presently a Fellow at the Radcliffe Institute of Advanced Study at Harvard University and at the Collegium Helveticum in Zurich. 
PACM Colloquium: Equiangular lines and spherical codes in Euclidean spacesSpeaker: Benny Sudakov, ETH Zürich Date: Feb 20 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: A family of lines through the origin in Euclidean space is called equiangular if any pair of lines defines the same angle. The problem of estimating the maximum cardinality of such a family in $\mathbb{R}^n$ was extensively studied for the last 70 years. Answering a question of Lemmens and Seidel from 1973, in this talk we show that for every fixed angle $\theta$ and sufficiently large $n$ there are at most $2n2$ lines in $\mathbb{R}^n$ with common angle $\theta$. Moreover, this is achievable only when $\theta =\arccos\frac{1}{3}$. Various extensions of this result to the more general settings of lines with $k$ fixed angles and of spherical codes will be discussed as well. Joint work with I. Balla, F. Drexler and P. Keevash. Benny Sudakov received his PhD from Tel Aviv University in 1999. He had appointments in Princeton University, the Institute for Advanced Studies and in UCLA, and is currently professor of mathematics in ETH, Zurich. He is the recipient of a Sloan Fellowship, NSF CAREER Award, Humboldt Research Award, is AMS Fellow and was invited speaker at the 2010 International Congress of Mathematicians. His main research interests are combinatorics and its applications to other areas of mathematics and computer science. 
PACM Colloquium: Sampling Nodes and Constructing Expanders LocallySpeaker: Silvio Lattanzi, Google Research Date: Feb 27 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: In many real world applications we have only limited access to networks. For example when we crawl a social network or we design a peertopeer system we are restricted to access nodes only locally. In this talk we will analyze two classic problems in this setting. First we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using only local random walks as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a neartight bound expressed in terms of the parameters of the graph such as average degree and the mixing time. Both theoretically and empirically, we show that some algorithms are preferable in practice than the others. We also extend our study to the problem of sampling nodes according to some polynomial function of their degrees; this has implications for designing efficient algorithms for applications such as triangle counting. Then we focus on the following classic distributed problem with applications to peertopeer networks. Given an nnode dregular network for d = Ω(log n), we want to design a decentralized, local algorithm that transforms the graph into one that has good connectivity properties (low diameter, expansion, etc.) without affecting the sparsity of the graph. To this end, Mahlmann and Schindelhauer introduced the random “flip” transformation, where in each time step, a random pair of vertices that have an edge decide to ‘swap a neighbor’. They conjectured that performing O(nd) such flips at random would convert any connected dregular graph into a dregular expander graph, with high probability. However, the best known upper bound for the number of steps is roughly O(n^17d^23), obtained via a delicate Markov chain comparison argument. Our main result is to prove that a natural instantiation of the random flip produces an expander in at most O(n^2d^2\sqrt{log n}) steps, with high probability. We also show that our technique can be used to analyze another wellstudied random process known as the ‘random switch’, and show that it produces an expander in O(nd) steps with high probability. (Joint work with Zeyuan AllenZhu, Aditya Bhaskara, Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Lorenzo Orecchia and Tamas Sarlos) Silvio Lattanzi is a Research Scientist in the Market Algorithm and Optimization group at Google New York since January 2011. He received his PhD in Computer Science from Sapienza University of Rome, advised by Alessandro Panconesi. During his PhD he interned twice at Google and once at Yahoo! Research. His research interests are in the areas of algorithms, machine learning and information retrieval. 
PACM Colloquium: How Far Are We From Having a Satisfactory Theory of Clustering?Speaker: Shai BenDavid, University of Waterloo Date: Mar 6 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Unsupervised learning is widely recognized as one of the most important challenges facing machine learning nowadays. However, unlike supervised learning, our current theoretical understanding of those tasks, and in particular of clustering, is very rudimentary. Although hundreds of clustering papers are being published every year, there is hardly any work reasoning about clustering independently of any particular algorithm, objective function, or generative data model. My talk will focus on such clustering research. I will discuss two aspects in which theory could play a significant role in guiding the use of clustering tools. The first is model selection  how should a user pick an appropriate clustering tool for a given clustering problem, and how should the parameters of such an algorithmic tool be tuned? In contrast with other common computational tasks, in clustering, different algorithms often yield drastically different outcomes. Therefore, the choice of a clustering algorithm may play a crucial role in the usefulness of an output clustering solution. However, there currently exist no methodical guidance for clustering tool selection for a given clustering task. I will describe some recent proposals aiming to address this crucial lacuna. The second aspect of clustering that I will address is the complexity of computing a cost minimizing clustering (given some clustering objective function). Once a clustering model (or objective) has been picked, the task becomes an optimization problem. While most of the clustering objective optimization problems are computationally infeasible, they are being carried out routinely in practice. This theorypractice gap has attracted significant research attention recently. I willdescribe some of the theoretical attempts to address this gap and discuss how close do they bring us to a satisfactory understanding of the computational resources needed for achieving good clustering solutions. The talk is based on joint work with my students Hassan Ashtiani and Shrinu Kushagra 
PACM Colloquium: Recent progress in object recognition and symmetry detection in digital imagesSpeaker: Peter Olver, University of Minnesota Date: Mar 13 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: I will survey developments in the application of invariants of various types, including differential invariant signatures and joint invariant histograms, for object recognition and symmetry detection in digital images. Recent applications, including automated jigsaw puzzle assembly and cancer detection, will be presented. BIO: Peter J. Olver received his Ph.D. from Harvard University in 1976 under the guidance of Prof. Garrett Birkhoff. After being a Dickson Instructor at the University of Chicago and a postdoc at the University of Oxford, he has been on the faculty of the School of Mathematics at the University of Minnesota since 1980, and a full professor since 1985. As of July, 2008, he has been serving as the Head of the Department. He has supervised 20 Ph.D. students to date, with 3 more currently supervised, as well as mentoring 23 postdocs and visiting students from around the world. He has also supervised 17 undergraduate research projects, many of which have led to publications. His research interests revolve around the applications of symmetry and Lie groups to differential equations. Over the years, he has done research in fluid mechanics, elasticity, quantum mechanics, mathematical physics, Hamiltonian mechanics, the calculus of variations, differential geometry, classical invariant theory, computer vision, and geometric numerical methods. He is the author of over 130 papers in refereed journals, and an additional 46 that appeared in conference proceedings. He was named a "Highly Cited Researcher'' by ThomsonISI in 2003. His research has received continuous NSF funding since 1981. He is the author of 5 books, including the definitive text on applications of Lie groups to differential equations, which was published in 1986, translated into Russian, and also republished in China. His most recent book is an undergraduate text on partial differential equations, published by Springer in 2014. 
PACM Colloquium: Stochastic Models in Robotics and Structural BiologySpeaker: Gregory Chirikjian, Johns Hopkins University Date: Mar 27 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Many stochastic problems of interest in engineering and science involve random rigidbody motions. In this talk, a variety of stochastic phenomena that evolve on the group of rigidbody motions will be discussed together with tools from harmonic analysis and Lie theory to solve the associated equations. These include mobile robot path planning, statistical mechanics of DNA, and problems in image processing. Current work on multirobot team diagnosis and repair, information fusion, and selfreplicating robots will also be discussed. In order to quantify the robustness of such robots, measures of the degree of environmental uncertainty that they can handle need to be computed. The entropy of the set of all possible arrangements (or configurations) of spare parts in the environment is such a measure, and has led us to study problems at the foundations of statistical mechanics and information theory. These, and other, topics in robotics and structural biology lend themselves to the same mathematical tools, which will be discussed in this talk. Gregory S. Chirikjian received undergraduate degrees from Johns Hopkins University in 1988, and the Ph.D. degree from the California Institute of Technology, Pasadena, in 1992. Since 1992, he has been on the faculty of the Department of Mechanical Engineering, Johns Hopkins University, where he has been a full professor since 2001. From 20042007 he served as department chair. His research interests include robotics, applications of group theory in a variety of engineering disciplines, and the mechanics of biological macromolecules. He is a 1993 National Science Foundation Young Investigator, a 1994 Presidential Faculty Fellow, and a 1996 recipient of the ASME Pi Tau Sigma Gold Medal. In 2008 he became a Fellow of the ASME, and in 2010 he became a Fellow of the IEEE. He is the author of more than 200 journal and conference papers and primary author on three books: Engineering Applications of Noncommutative Harmonic Analysis (2001) and Stochastic Models, Information Theory, and Lie Groups, Vols. 1+2. (2009,2011). In 2016 and expanded edition of his 2001 book came out as a Dover book under the new title: Harmonic Analysis for Engineers and Applied Scientists. 
PACM Colloquium: Sampleoptimal inference, computational thresholds, and the methods of momentsSpeaker: David Steurer, Cornell University Date: Apr 3 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: We propose an efficient metaalgorithm for Bayesian inference problems based on lowdegree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sumofsquares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lowerorder terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for partial recovery in the stochastic block model, a widelystudied class of inference problems for community detection in graphs. We obtain the first partial recovery guarantees for the mixedmembership stochastic block model (Airoldi et el.) for constant average degree—up to what we conjecture to be the computational threshold for this model. Our algorithm also captures smooth tradeoffs between sample and computational complexity, for example, for tensor principal component analysis. In contrast, we show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten–Stigum bound—giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the bestpossible lowdegree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments. Joint work with Samuel B. Hopkins (Cornell). David Steurer is an Assistant Professor in the department of computer science at Cornell University and a Visiting Assistant Professor at the Institute for Advanced Study in Princeton. His research interests are in the theory of algorithms, complexity, and machine learning. Steurer received his PhD from Princeton University advised by Sanjeev Arora and was a postdoctoral researcher at Microsoft Research for two years before joining Cornell University. For his work, he received an ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award, and an Alfred P. Sloan Research Fellowship, a Microsoft Research Faculty Fellowship, and best paper awards at STOC and FOCS.

PACM Colloquium: Physics in the complex planeSpeaker: Carl M. Bender, Washington University in St. Louis Date: Apr 10 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: The average quantum physicist on the street would say that a quantummechanical Hamiltonian must be Dirac Hermitian (invariant under combined matrix transposition and complex conjugation) in order to guarantee that the energy eigenvalues are real and that time evolution is unitary. However, the Hamiltonian $H=p^2+ix^3$, which is obviously not Dirac Hermitian, has a positive real discrete spectrum and generates unitary time evolution, and thus it defines a fully consistent and physical quantum theory. Evidently, the axiom of Dirac Hermiticity is too restrictive. While $H=p^2+ix^3$ is not Dirac Hermitian, it is PT symmetric; that is, invariant under combined parity P (space reflection) and time reversal T. The quantum mechanics defined by a PTsymmetric Hamiltonian is a complex generalization of ordinary quantum mechanics. When quantum mechanics is extended into the complex domain, new kinds of theories having strange and remarkable properties emerge. In the past few years, some of these properties have been observed and verified in laboratory experiments. A particularly interesting PTsymmetric Hamiltonian is $H=p^2x^4$, which contains an upsidedown potential. We explain in intuitive and in rigorous terms why the energy levels of this potential are real, positive, and discrete. 
PACM Colloquium: Tractable approximations to nonnegative polynomials with applications to the joint spectral radiusSpeaker: Amir Ali Ahmadi, Princeton University Date: Apr 24 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: The problem of recognizing nonnegativity of a multivariate polynomial has a celebrated history, tracing back to Hilbert’s 17th problem. In recent years, there has been much renewed interest in the topic because of a multitude of applications in applied and computational mathematics and the observation that one can optimize over an interesting subset of nonnegative polynomials using “sum of squares (SOS) optimization”. In this talk, we give a brief overview of the developments in this field and then focus on two recent results. In part (i), we show that the joint spectral radius of a finite set of matrices is less than one if and only if there exists a polynomial norm (i.e., a norm which is the dth root of a degreed homogeneous polynomial) that decreases under the application of all matrices. Moreover, the convexity of this polynomial and its decrease inequalities can all be verified using SOS certificates. This result generalizes the classical theorem in linear algebra that the spectral radius of a matrix is less than one if and only if there exists a decreasing quadratic norm. In part (ii), we introduce new algebraic sufficient conditions for polynomial nonnegativity that are very similar to the SOS condition but instead of semidefinite programs lead to linear or second order cone programs when implemented numerically. These are what we call ``DSOS and SDSOS programs.’’ We show that these relaxations are orders of magnitude more scalable than the SOS relaxation while enjoying many of the same asymptotic theoretical guarantees. Joint work (in different subsets) with Etienne de Klerk, Georgina Hall, Raphael Jungers, and Anirudha Majumdar. Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) is an Assistant Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Department of Computer Science. Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamics and control, and algorithms and complexity. Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ``Computing and Optimization’’) has received the 2017 Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers. Amir Ali is also the recipient of a number of bestpaper awards, including the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Control and Optimization in 20132015. 
Fall 2016
PACM Colloquium: Nonlinear echoes and Landau damping with insufficient regularitySpeaker: Jacob Bedrossian, University of Maryland Date: Sep 19 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: In this talk, we will discuss recent advances towards understanding the regularity hypotheses in the theorem of Mouhot and Villani on Landau damping near equilibrium for the VlasovPoisson equations. We show that, in general, their theorem cannot be extended to any Sobolev space on the 1D torus. This is demonstrated by constructing arbitrarily small solutions with a sequence of nonlinear oscillations, known as plasma echoes, which damp at a rate arbitrarily slow compared to the linearized Vlasov equations. Some connections with hydrodynamic stability problems will be discussed if time permits. Bio: Jacob earned his PhD in 2011 from UCLA under advisors Andrea Bertozzi and Joey Teran. He went on to the Courant Institute as an NSF postdoc and in 2014 he joined the faculty at the University of Maryland, College Park. In 2015 he received a Sloan research fellowship and in 2016 he was awarded an NSF CAREER grant. Most of his research is focused on hydrodynamic stability at high Reynolds number and collisionless kinetic theory, but has also included the analysis of KellerSegel models from mathematical biology, calculus of variations, and scientific computing. 
PACM Colloquium: Efficient Numerical Methods for Thermodynamic Averaging and Statistical InferenceSpeaker: Benedict Leimkuhler, University of Edinburgh Date: Sep 26 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Molecular models and data analytics problems give rise to gargantuan systems of stochastic differential equations (SDEs) whose paths ergodically sample multimodal probability distributions. An important challenge for the numerical analyst (or the chemist, or the physicist, or the engineer, or the data scientist) is the design of efficient numerical methods to generate these paths. For SDEs, the numerical perspective is just maturing, with important new methods (and, even more important, new procedures for their construction and analysis) becoming available. One of the interesting ideas is to design stochastic schemes with close attention to the error in invariant measures. Another is to use negative feedback loop controls to regulate a noisy gradient or even the discretisation error itself. To illustrate our approach, I will discuss several different examples including (i) efficient schemes for constrained stochastic dynamics improving accuracy and stability in bioMD [1,2], and (ii) methods for Bayesian sampling for machine learning applications [3]. If time permits, I will also describe some very recent work on parallel sampling algorithms [4]. [1] B. Leimkuhler and C. Matthews, Rational construction of stochasticnumerical methods for molecular sampling, Applied Mathematics Research Express, 2013. [2] B. Leimkuhler and C. Matthews, Efficient molecular dynamics using geodesic integration and solventsolute splitting, Proceedings of the Royal Society A, 2016. [3] X. Shang, Z. Zhu, B. Leimkuhler and A. Storkey, Covariancecontrolled adaptive Langevin thermostat for largescale Bayesian sampling, Neural and Information Processing Systems (NIPS) 2015. [4] B. Leimkuhler, C. Matthews and J. Weare, Ensemble preconditioning for Markov chain Monte Carlo simulation, Arxiv: https://arxiv.org/abs/1607.03954 Bio: Ben Leimkuhler is the Chair of Applied Mathematics at the University of Edinburgh. He received his PhD from the University of Illinois under the direction of C.W. Gear and worked in Helsinki and then at the Universities of Kansas and Leicester before moving to Scotland in 2006. He is well known for his work on the foundations of algorithms for dynamical modelling and sampling, much of it surveyed in two books: Leimkuhler and Reich, Simulating Hamiltonian Dynamics, CUP, 2005 (deterministic methods), Leimkuhler and Matthews, Molecular Dynamics, Springer, 2015 (mostly stochastic methods). He is also a Faculty Fellow of the nascent Alan Turing Institute, a major centre for research in “data science” and the intellectual hub of the London Knowledge Quarter. 
PACM Colloquium: Network clustering with higher order structuresSpeaker: David Gleich, Purdue University Date: Oct 3 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Spectral clustering is a wellknown way to partition a graph or network into clusters or communities with provable guarantees on the quality of the clusters. This guarantee is known as the Cheeger inequality and it holds for undirected graphs. We'll discuss a new generalization of the Cheeger inequality to higherorder structures in networks including network motifs. This is easy to implement and seamlessly generalizes spectral clustering to directed, signed, and many other types of complex networks. In particular, our generalization allow us to reuse the large history of existing ideas in spectral clustering including local methods, overlapping methods, and relationships with kernel kmeans. We will illustrate the types of clusters or communities found by our new method in biological, neuroscience, ecological, transportation, and social networks. Bio: 
PACM Colloquium: Optics and optimizationSpeaker: Eitan Bachmat, BenGurion University (Israel) Date: Oct 10 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: We will consider the following airplane boarding policy which was recently implemented by a few airlines: "Passengers with no overhead bin luggage board before those with such luggage" The reasoning for the policy was explained by the CEO of one of the companies as follows. Passengers with no overhead bin luggage tend to occupy the aisle for less time, therefore by boarding them first, the airline is able to push more people more quickly into the airplane, thus expediting the boarding process as a whole. In the talk we will show that what the airline wanted to do is to construct a thin focal lens in some spacetime domain. Unfortunately, the shapes that correspond to the airline's policy are neither focal nor thin. In the talk we will construct nice some lenses, discuss the airplane boarding implications and consider some higher dimensional analogues which exhibit concentration of measure. The talk will be self contained. In preparation for the talk, I recommend flying as much as possible and answering the following question. Rank the following 3 policies by boarding time speed starting with the fastest A. Board slow passengers first. B. Board fast passengers first. C. Do not separate passengers, just let them board. 
PACM Colloquium: Testing Distribution PropertiesSpeaker: Costantinos Daskalakis Date: Oct 17 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Given samples from an unknown distribution p, is it possible to distinguish whether p belongs to some class of distributions C versus p being far from every distribution in C by some margin? This fundamental question has received extensive study in Statistics, Computer Science and several other fields. Still, even for basic classes of distributions such as unimodal, logconcave, or product the optimal sample complexity is unknown. We provide optimal testers for these and other families. In the process we strengthen the exchangeable pairs framework of [Chatterjee 2005]. (Based on works with Jayadev Acharya, Nishanth Dikkala, Gautam Kamath) 
PACM Colloquium: Counting Connected GraphsSpeaker: Joel Spencer, New York University Date: Oct 24 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Let C(n,k) be the number of labelled connected graphs with n vertices and n1+k edges. For k=0 (trees) we have Cayley's Formula. We examine the asymptotics of C(n,k). There are several approaches involving supercritical dominant components in random graphs, local limit laws, Brownian excursions, Parking functions and other topics. 
PACM Colloquium: Statistics, Machine Learning, and Understanding the 2016 ElectionSpeaker: Samuel Wang, Princeton University Date: Nov 7 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Video to view lecture: http://www.kaltura.com/tiny/msbd6 Although 2016 is a highly unusual political year, elections and public opinion follow predictable statistical properties. I will review how the Presidential, Senate, and House races can be tracked and forecast from freely available polling data. Missing data can be filled in using a GoogleWide Association Study (GoogleWAS). Finally, simple statistics can be used to identify inequities such as partisan gerrymandering, and provide a tool for possible judicial relief. These examples show how statistics and machine learning can deepen an understanding of the U.S. political scene, even under extreme circumstances. Samuel S.H. Wang, Ph.D., Professor, Neuroscience Institute and Department of Molecular Biology, Princeton University

PACM Colloquium: How Well Do Local Algorithms Solve Semidefinite Programs?Speaker: Andrea Montanari, Stanford University Date: Nov 14 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Several probabilistic models from highdimensional statistics and machine learning reveal an intriguing and yet poorly understood dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semidefinite programming (SDP) relaxations fail. In order to explore this phenomenon, we study a classical SDP relaxation of the minimum graph bisection problem, when applied to ErdosRenyi random graphs with bounded average degree d>1, and obtain several types of results. First, we use a dual witness construction (using the socalled nonbacktracking matrix of the graph) to upper bound the SDP value. Second, we prove that a simple local algorithm approximately solves the SDP to within a factor 2d^2/(2d^2+d−1) of the upper bound. In particular, the local algorithm is at most 8/9 suboptimal, and 1+O(1/d) suboptimal for large degree. We then analyze a more sophisticated local algorithm, which aggregates information according to the harmonic measure on the limiting GaltonWatson (GW) tree. The resulting lower bound is expressed in terms of the conductance of the GW tree and matches surprisingly well the empirically determined SDP values on largescale ErdosRenyi graphs. We finally consider the planted partition model. In this case, purely local algorithms are known to fail, but they do succeed if a small amount of side information is available. Our results imply quantitative bounds on the threshold for partial recovery using SDP in this model. 
PACM Colloquium: Kernelbased methods for Bandit Convex OptimizationSpeaker: Ronen Eldan, Weizmann Institute of Science Date: Nov 21 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: I will present the first polytime and regret algorithm for bandit convex optimization. Consider the problem of optimizing a unknown convex function using an approximate function value oracle. In the stochastic approximation literature one usually assumes that the noise is zeromean, identical and independent between queries. The bandit framework goes much beyond this independence assumption by saying that for each query there is a different function (potentially chosen adversarially given all the past choices) and the objective is to optimize the average function. The problem at hand is thus formulated as follows: given a convex body , the problem can be described as the following sequential game: at each time step , a player selects an action , and simultaneously an adversary selects a convex loss function . The player's feedback is its suffered loss, . The player has access to external randomness, and can select her action based on the history . The player's perfomance at the end of the game is measured through the regret which compares her cumulative loss to the smallest cumulative loss she could have obtained had she known the sequence of loss functions. We will present the first algorithm which achieves optimal dependence of $T$ and a polynomial dependence on the dimension. This new algorithm is based on three ideas: (i) kernel methods, (ii) a generalization of Bernoulli convolutions (this a selfsimilar process that has been studied since the 1930's, most notably by Erdos), and (iii) a new annealing schedule for exponential weights (with increasing learning rate). Joint w. Sebastien Bubeck and YinTat Lee. 
PACM Colloquium: Concurrent Disjoint Set UnionSpeaker: Robert Tarjan, Princeton University Date: Nov 28 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compareandswap primitives for synchronization, making them waitfree. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton. Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms. 
PACM Colloquium: Turbulent weak solutions of the Euler equationsSpeaker: Vlad Vicol Date: Dec 5 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Motivated by Kolmogorov's theory of hydrodynamic turbulence, we consider dissipative weak solutions to the 3D incompressible Euler equations. We show that there exist infinitely many weak solutions of the 3D Euler equations, which are continuous in time, lie in a Sobolev space $H^s$ with respect to space, and they do not conserve the kinetic energy. Here the smoothness parameter $s$ is at the Onsager critical value $1/3$, consistent with Kolmogorov's $4/5$ law for the third order structure functions. We shall also discuss bounds for the second order structure functions, which deviate from the classical Kolmogorov 1941 theory. This talk is based on joint work with T. Buckmaster and N. Masmoudi. 
PACM Colloquium: Quantum Oracle Classification: The Case of Group StructureSpeaker: Mark Zhandry, Princeton University Date: Dec 12 2016  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems. In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space. Moreover, there is a homomorpism f on A, and the goal is to determine f(A). This class of problems is very general, and covers several interesting cases, such as oracle evaluation; polynomial interpolation, evaluation, and extrapolation; and parity. These problems are important in the study of message authentication codes in the quantum setting, and may have other applications. We exactly characterize the quantum query complexity of every instance of QOC with group structure in terms of a particular counting problem. That is, we provide an algorithm for this general class of problems whose success probability is determined by the solution to the counting problem, and prove its exact optimality. Unfortunately, solving this counting problem in general is a nontrivial task, and we resort to analyzing special cases. Our bounds unify some existing results, such as the existing oracle evaluation and parity bounds. In the case of polynomial interpolation and evaluation, our bounds give new results for secret sharing and information theoretic message authentication codes in the quantum setting. ______________________ Mark Zhandry received his bachelor’s degree from UC Berkeley, where he majored in electrical engineering, computer science, and physics, and minored in mathematics. He earned his PhD in computer science in 2015 from Stanford University, and subsequently was a postdoctoral associate at MIT. Since Summer 2016, he is an assistant professor in the computer science department at Princeton University. His main research area is cryptography, with focuses on software obfuscation and the impacts of quantum computers to cryptography. 