Queens College CUNY Computer Science Colloquium

- Monday, 02/05/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Shubham Jain, Stony Brook University**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.

- Monday, 02/26/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Guy Moshkovitz, Baruch College, CUNY**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.

- Wednesday, 02/28/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Reilly Browne, Stony Brook University**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.

- Monday, 03/04/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Nicola Guglielmi, Gran Sasso Science Institute, Italy**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).

- Monday, 03/18/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Tamalika Mukherjee, Columbia University**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.

- Monday, 03/25/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Michael Overton, New York University**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.

- Monday, 04/08/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Xianfeng Gu, Stony Brook University**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.

- Monday, 04/15/2024, 12:15PM - 1:30PM

Science Building, C205

Speaker: Matthias Voigt, UniDistance Suisse, Brig, Switzerland**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.

The seminar is organized by Mayank Goswami

Email Contact: mayank.goswami@qc.cuny.edu