Title: From Macro to Micro: Understanding Human Motion In the Wild
Abstract: Modern environments are alive with sensors, such as smartphones, wearables, vehicles, and cameras. However, despite the plethora of sensors, direct sensing of desired events is difficult in the real-world. This is primarily due to large amounts of noise introduced by our movements during everyday tasks, in addition to lack of dedicated sensors and deployment difficulties. We address this challenge by modeling movements to design and develop mobility-aware systems. This has opened up new opportunities in both urban tech and mobile health. This talk will explore our research efforts in leveraging pervasive sensing devices, towards developing a multi-modal data integration and interpretation framework. I will discuss sensing frameworks for urban spaces and the mHealth space. We have designed real-time monitoring tools that can capture fine-grained measures of users’ health in uncontrolled environments. In building these data-driven frameworks that introduce mobility-awareness in non-homogeneous sensors, we introduce new avenues for smart cities and healthcare analytics in the real-world.
Title: Recent progress in the study of tensor ranks
Abstract: While for matrices there is one notion of rank with many equivalent definitions, for tensors (a.k.a. higher-dimensional matrices) there are many inequivalent notions. Understanding the interplay between these notions is closely related to important questions in additive combinatorics, algebraic geometry, and computer science. In this talk I will discuss recent (exciting!) progress in the study of tensor ranks from the last few years.
Title: Constant factor approximation algorithms for convex cover and hidden set in simple polygons
Abstract: Two fundamental classes of problems in theoretical computer science and especially computational geometry are packing problems and covering problems. Packing problems ask for the maximum number of elements fit into a domain whereas covering problems ask for the minimum number of elements to cover a domain. We explore a covering problem and a packing problem in polygon visibility, called minimum convex cover and maximum hidden set respectively.
Given a simple polygon P, the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P. The maximum hidden set problem seeks to place within P a max- imum cardinality set of points no two of which see each other. In this talk, I will describe our constant factor approximation algorithms for both problems. Previously, the best approximation factor for the minimum convex cover was logarithmic; for the maximum hidden set problem, no approximation algorithm was known. I also will discuss how to extend these results further into more specific classes of polygons such as star-shaped polygons and orthogonal polygons.
Title: Solving numerically differential equations with distributed delays.
Abstract: Models with distributed delays are of increasing importance in pharmacodynamics and pharmacokinetics for the study of the interaction between drugs and the body. However, their numerical integration is considered a challenging task.
There exist efficient codes for the numerical treatment of stiff and differential-algebraic problems (e.g. Radau5), and also in the case where these equations present discrete delays (e.g. Radar5), which are based on implicit integrators, as collocation methods. The aim of the present work is to present a technique that permits a direct application of these codes to a class of problems having a right-hand side with an additional distributed delay term (which is a special case of an integro-differential equation).
The main idea of this work is to approximate the distribution kernel of the integral term by a sum of exponential functions or by a quasi-polynomial expansion, and then to transform the distributed (integral) delay term into a set of ordinary differential equations.
The original equations augmented by this set of ordinary differential equations are stiff and can have a very large dimension; therefore a careful treatment of the solution of the linear systems associated with every step of the method is very important. The use of the code Radau5 is illustrated with two examples (one test equation and one problem taken from pharmacodynamics). The driver programs for these examples are publicly available from the homepages of the authors.
This is a joint work with Ernst Hairer (Geneva).
Title: How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
Abstract: We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on algorithms $A$ that output an approximation to a function $f$ of the form $(1-\alpha)f(x)-\kappa\leq A(x) \leq (1+\alpha)f(x)+\kappa$, where $\kappa \in \mathbb{R}_{\geq 0}$ denotes additive error and $\alpha\in [0,1)$ denotes multiplicative error can be "tuned" to small-enough values while incurring only a polynomial blowup in the running time/space. We show that such algorithms can be made differentially private without sacrificing accuracy, as long as the function $f$ has small "global sensitivity". We achieve these results by applying the "smooth sensitivity" framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007).
Our framework naturally applies to transform non-private FPRAS and FPTAS algorithms into $\varepsilon$-differentially private approximation algorithms where the former case requires an additional postprocessing step. We apply our framework in the context of sublinear-time and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) $\epsilon$-edge differentially-private sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a minimum spanning tree of a graph whose accuracy holds with high probability.
In the area of streaming algorithms, our results include $\epsilon$-DP algorithms for estimating $L_p$-norms, distinct elements, and weighted minimum spanning tree for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating $L_p$-norms, distinct elements, and the length of the longest increasing subsequence.
Title: Crouzeix’s Conjecture
Abstract:
Crouzeix's conjecture is among the most intriguing developments in matrix theory in recent years.
Made in 2004 by Michel Crouzeix, it postulates that, for any polynomial $p$ and any matrix $A$,
$\|p(A)\| \le 2 \max\{|p(z)|: z \in W(A)\}$, where the norm is the 2-norm and $W(A)$ is the field
of values (numerical range) of $A$, that is the set of points attained by $v^*Av$ for some
vector $v$ of unit length. Crouzeix proved in 2007 that the inequality above
holds if 2 is replaced by 11.08, and in 2016 this was greatly improved by Palencia,
replacing $2$ by $1+\sqrt{2}$. Furthermore, it is known that the conjecture holds in a
number of special cases. We use nonsmooth optimization to investigate
the conjecture numerically by locally minimizing the "Crouzeix ratio", defined as the
quotient with numerator the right-hand side and denominator the left-hand side of the
conjectured inequality. We use Chebfun to compute the boundary of the fields of values and
BFGS for the optimization, computing the Crouzeix ratio at billions of data points.
We also present local nonsmooth variational analysis of the
Crouzeix ratio at conjectured global minimizers. All our results strongly support the
truth of Crouzeix's conjecture.
Title: A Geometric View of Optimal Transport and Sora
Abstract: Generative models have achieved tremendous success,
particularly the text-to-video generative model Sora, which has
garnered significant attention. However, the videos generated by Sora
contain numerous physical errors, which can be summarized as
contradictions between correlation and causality, local coherence and
global absurdity, and the absence of critical states, among others. In
this talk, we will interpret the optimal transport theory from a
geometric viewpoint and apply it to generative models. This will be
used to analyze the principles behind Sora, identify the intrinsic
reasons for Sora's physical mistakes, and propose methods for further
improvement.
Title: Introduction to Structure-Preserving Model Order Reduction of Dynamical Systems
Abstract: Model order reduction is a field of mathematics that deals with the complexity reduction of mathematical models in order to reduce the computational costs of tasks such as numerical simulation, optimization, or control. In this talk, first an overview of the field will be given and one of the classical systems theoretic reduction methods (balanced truncation) will be reviewed. The second part of the presentation will focus on structure-preserving reduction methods for structured models. This includes a variant of balanced trunction for symmetric second-order systems and, if time allows, a rational fitting method for the class of port-Hamiltonian systems.