[CV: Prof. Oded Margalit has a PhD in computer science from Tel Aviv University under the supervision of Prof. Zvi Galil. He has worked at IBM Research – Haifa in the areas of machine learning, constraint satisfaction, verification, and more. Currently, he is the CTO of the IBM Cybersecurity Center of Excellence in Beer Sheva, Israel. Oded helps organize several computer science competitions, like the international IEEEXtreme and the Israeli national CodeGuru competition. He loves riddles and authors the IBM Research monthly challenge corner Ponder This.]
Seminars and Colloquia by Series
Friday, November 16, 2018 - 11:00 , Location: Skiles 006 , Mark Rudelson , University of Michigan , email@example.com , Organizer: Galyna Livshyts
Thursday, October 25, 2018 - 11:00 , Location: Skiles 006 , Gábor Lugosi , Pompeu Fabra University, Barcelona , Organizer: Mayya Zhilova
In these lectures we discuss some statistical problems with an interesting combinatorial structure behind. We start by reviewing the "hidden clique" problem, a simple prototypical example with a surprisingly rich structure. We also discuss various "combinatorial" testing problems and their connections to high-dimensional random geometric graphs. Time permitting, we study the problem of estimating the mean of a random variable.
Thursday, September 27, 2018 - 11:00 , Location: Skiles 006 , Igor Pak , UCLA , Organizer: Mayya Zhilova
Given a convex polytope P, what is the number of integer points in P? This problem is of great interest in combinatorics and discrete geometry, with many important applications ranging from integer programming to statistics. From computational point of view it is hopeless in any dimensions, as the knapsack problem is a special case. Perhaps surprisingly, in bounded dimension the problem becomes tractable. How far can one go? Can one count points in projections of P, finite intersections of such projections, etc? We will survey both classical and recent results on the problem, emphasizing both algorithmic and complexity aspects. Some elegant hardness results will make an appearance in dimension as small as three. If time permits, we will discuss connections to Presburger Arithmetic and decidability problems for irrational polyhedra. Joint work with Danny Nguyen.
Thursday, September 20, 2018 - 11:00 , Location: Skiles 006 , Blair Sullivan , Department of Computer Science, NC State University , Organizer: Christine Heitsch
Techniques from structural graph theory hold significant promise for designing efficient algorithms for network science. However, their real-world application has been hampered by the challenges of unrealistic structural assumptions, hidden costs in big-O notation, and non-constructive proofs. In this talk, I will survey recent results which address many of these concerns through an algorithmic pipeline for structurally sparse networks, highlighting the crucial role of certain graph colorings, along with several open problems. For example, we give empirical and model-based evidence that real-world networks exhibit a form of structural sparsity known as "bounded expansion,'' and discuss properties of several low-treedepth colorings used in efficient algorithms for this class. Based on joint works with E. Demaine, J. Kun, M. O'Brien, M. Pilipczuk, F. Reidl, P. Rossmanith, F. Sanchez Villaamil, and S. Sikdar.
Tuesday, September 4, 2018 - 11:00 , Location: Skiles 006 , Sara van de Geer , ETH Zurich , Organizer: Mayya Zhilova
The colloquium will be the second lecture of the TRIAD Distinguished Lecture Series by Prof. Sara van de Geer. For further information please see http://math.gatech.edu/events/triad-distinguished-lecture-series-sara-van-de-geer-0.
Wednesday, June 6, 2018 - 15:30 , Location: Skiles 006 , Sarah Koch , U Michigan , Organizer: Dan Margalit
Given two complex polynomials, we can try to mathematically paste them together to obtain a rational function through a procedure known as mating the polynomials. In this talk, we will begin by trying to understand the "shape" of complex polynomials in general. We will then discuss the mating of two quadratic polynomials: we explore examples where the mating does exist, and examples where it does not. There will be lots of movies and exploration in this talk.
Thursday, April 19, 2018 - 11:00 , Location: Skiles 006 , Tim Austin , UCLA Mathematics Department , Organizer: Mayya Zhilova
This talk is about the structure theory of measure-preserving systems: transformations of a finite measure space that preserve the measure. Many important examples arise from stationary processes in probability, and simplest among these are the i.i.d. processes. In ergodic theory, i.i.d. processes are called Bernoulli shifts. Some of the main results of ergodic theory concern an invariant of systems called their entropy, which turns out to be intimately related to the existence of `structure preserving' maps from a general system to Bernoulli shifts. I will give an overview of this area and its history, ending with a recent advance in this direction. A measure-preserving system has the weak Pinsker property if it can be split, in a natural sense, into a direct product of a Bernoulli shift and a system of arbitrarily low entropy. The recent result is that all ergodic measure-preserving systems have this property. This talk will assume graduate-level real analysis and measure theory, and familiarity with the basic language of random variables. Past exposure to entropy, measure-theoretic probability or ergodic theory will be helpful, but not essential.
Tuesday, April 10, 2018 - 11:00 , Location: Skiles 006 , Prof. Oded Margalit , CTO, IBM Cybersecurity Center of Excellence, Beer Sheva, Israel , Organizer: Lutz Warnke
For the sake of puzzle-lovers worldwide, IBM Research offers a monthly mathematical challenge known as Ponder This. Every month, a new challenge is posted together with the solution for the previous month's riddle. Prof. Oded Margalit has served as the Ponder This puzzlemaster for the last decade. In this talk, he’ll survey some of most interesting riddles posted over the years, and tell some anecdotes about various challenges and regular solvers, such as one person who sent in his solution from an intensive care unit. Several challenges have led to conference and journal papers, such as a PRL paper born from a riddle on random walks, and an ITA 2014 paper on a water hose model (using quantum entanglement to break location-based encryption). Other monthly challenges have riffed on games such as 2048, Kakuro, an infinite chess game, the probability of backgammon ending with a double, Fischer Random Chess, and more. Other challenges have been more purely mathematic, focusing on minimal hash functions, combinatorial test design, or finding a natural number n such that round ((1+2 cos(20))^n) is divisible by 10^9. The talk will present a still-open question about a permutation-firing cannon. The talk will be self contained.
Thursday, March 8, 2018 - 11:00 , Location: Skiles 006 , Santosh Vempala , Georgia Institute of Technology, College of Computing, ISYE, Math , Organizer: Mayya Zhilova
The KLS conjecture says that the Cheeger constant of any logconcave density is achieved to within a universal, dimension-independent constant factor by a hyperplane-induced subset. Here we survey the origin and consequences of the conjecture (in geometry, probability, information theory and algorithms) and present recent progress resulting in the current best bound, as well as a tight bound for the log-Sobolev constant (both with Yin Tat Lee). The conjecture has led to several techniques of general interest.
Friday, March 2, 2018 - 11:00 , Location: Skiles 006 , Jill Pipher , Brown University , Organizer: Mayya Zhilova
The regularity properties of solutions to linear partial differential equations in domains depend on the structure of the equation, the degree of smoothness of the coefficients of the equation, and of the boundary of the domain. Quantifying this dependence is a classical problem, and modern techniques can answer some of these questions with remarkable precision. For both physical and theoretical reasons, it is important to consider partial differential equations with non-smooth coefficients. We’ll discuss how some classical tools in harmonic and complex analysis have played a central role in answering questions in this subject at the interface of harmonic analysis and PDE.