Date/Time : 26 Aug 2020 17:00
Venue : via Zoom
Speaker : Gordon Hoi,

Join  Zoom Meeting: https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assigned to be 1 and the other literals in the same clause are set to 0. If we restrict the length of each clause to be at most 3 literals, then it is known as the X3SAT problem. In this paper, we consider the problem of counting the number of satisfying assignments to the X3SAT problem, which is also known as #X3SAT. The current state of the art exact algorithm to solve #X3SAT is given by Dahlloef, Jonsson and Beigel and runs in O(1.1487^n), where n is the number of variables in the formula. In this paper, we propose an exact algorithm for the #X3SAT problem that runs in O(1.1120^n) with very few branching cases to consider, by using a result from Monien and Preis to give us a bisection width for graphs with at most degree 3. URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Add to calendar :

Date/Time : 19 Aug 2020 17:00
Venue : via Zoom
Speaker : Cristian Calude, University of Auckland

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: We present a new ternary QRNG based on measuring located value indefinite observables with probabilities <b>1/4,1/2,1/4</b> and prove that every sequence generated is maximally unpredictable, 3-bi-immune (a stronger form of bi-immunity), and its prefixes are Borel normal. The ternary quantum random digits produced by the QRNG are algorithmically transformed into quantum random bits using an alphabetic morphism which preserves all the above properties.

Add to calendar :

Date/Time : 19 Aug 2020 16:00
Venue : via Zoom
Speaker : Pang Tongyao , National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/97080214054?pwd=cnJtSXF0YTZWZ1U2QU5YQWpwaU1tUT09 Meeting ID: 970 8021 4054 Password: 632494 Abstract: In this talk, I will start with the classical sparse estimation, whih has been extensively studied and applied to a wide range of applications, e.g., image restoration, in the past few decades. While most of the existing methods targeted at solving a maximum a posterior (MAP) variational model with the sparsity prior, we proposed to find the minimum mean square error (MMSE) solution which provides a good balance between sparsity and unbiasedness. We develop a coordinate minimization algorithm and connect it to a variational model to establish a comprehensive convergence analysis. In recent years, deep learning has shown its advantages over the traditional sparsity prior based methods for image restoration problems. However, most deep learning methods are supervised which require a high-quality training dataset. Bringing the idea of Bayesian inference from sparse estimation to deep learning further, we are able to develop a self-supervised deep learning method that calls no other training samples but still achieves SOTA performance. The key to success of our method lies in the approximation to the MMSE estimate, which helps to reduce model bias and enables ensemble prediction scheme with lower variance.

Add to calendar :

Date/Time : 19 Aug 2020 10:00
Venue : via Zoom
Speaker : Junho Peter Whang, MIT

Join Zoom Meeting https://nus-sg.zoom.us/j/94766702852?pwd=UG9SclBVcTVlVDFnSnRQcFJjaUw4QT09 Meeting ID: 947 6670 2852 Password: 569325 Abstract: Moduli spaces for special linear rank two local systems (with prescribed boundary traces) on a topological surface are basic objects in geometry. The study of integer points on these algebraic varieties can be traced back to 1880 work of Markoff, in the case where the surface is a one-holed torus. For general surfaces, we will show that the moduli spaces are log Calabi-Yau, and use mapping class group dynamics and differential geometric tools to establish a structure theorem for their integer points. In addition, we will also give an analysis of algebraic curves on the moduli spaces. Throughout the talk, emphasis will be put on the interplay between the dynamical, arithmetic, and topological aspects of surfaces and their local systems.  

Add to calendar :

Date/Time : 14 Aug 2020 09:00
Venue : via Zoom
Speaker : Hong Wang , Institute for Advanced Study, Princeton

Join Zoom Meeting Meeting ID: 932 7338 0910 Password: 451089  Let $E$ be an $s$–dimensional set on the plane. How large is its distance set $\Delta(E):= \{ |x-y|, x, y\in E\}$?  Falconer conjectured in 1985 that if $s>1$, then $\Delta(E)$ should have positive Lebesgue measure.  We are going to discuss how this problem is connected to various problems in harmonic analysis, as well as different approaches toward it.

Add to calendar :

Date/Time : 12 Aug 2020 16:00
Venue : via Zoom
Speaker : Dong Bin, Peking University

Join Zoom Meeting https://nus-sg.zoom.us/j/93373644793?pwd=Y2VrdnJRazZnRXllN2N5K1BneWE1UT09 Meeting ID: 933 7364 4793 Password: 711028 In this talk, I will start with a brief review of the dynamics and optimal control perspective on deep learning (including supervised learning, reinforcement learning, and meta-learning), especially the so-called unrolled dynamics approach and its applications in medical imaging. Then, I will present some of our recent studies on how this new approach may help us to advance CT imaging and image-based diagnosis further. Specifically, I will focus on our thoughts on how to combine the wisdom from mathematical modeling with ideas from deep learning. Such combination leads to new data-driven image reconstruction models and new data-driven scanning strategies for CT imaging, and with a potential to be generalized to other imaging modalities.

Add to calendar :

Date/Time : 12 Aug 2020 17:00
Venue : via Zoom
Speaker : Frank Stephan, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/94862783492?pwd=eUo0aUdialQrZkt1dDlFNnB4QmtDdz09 Meeting ID: 948 6278 3492 Password: 811969  The initial segment complexity of a measure mu at n is given by the sum over all mu(x)*C(x) with x of length n for the plain complexity C and similarly for the prefix-free Kolmogorov complexity. This talk gives the basic relations between initial segment complexity and randomness notions and lists out various open questions which arise from this work. The same work was presented at the American Institute of Mathematics in this week’s programme on Algorithmic Randomness.

Add to calendar :

Date/Time : 31 Jul 2020 09:00
Venue : via Zoom
Speaker : Hao Huang , Emory University

Join Zoom Meeting  Meeting ID: 995 2080 5067 Password: 103513   Extremal Combinatorics studies how large or how small a collection of finite objects could be, if it has to satisfy certain restrictions. In this talk, we will discuss how the eigenvalue interlacing methods could lead to various interesting results in Extremal Combinatorics, including the Erdos-Ko-Rado Theorem and its degree version, an isodiametric inequality for discrete cubes, and the resolution of a thirty-year-old problem in Theoretical Computer Science, the Sensitivity Conjecture.

Add to calendar :

Date/Time : 17 Jul 2020 0900
Venue : via Zoom
Speaker : Yao Yao, Georgia Institute of Technology

Join Zoom Meeting Meeting ID: 940 7048 1887 Password: 5470853 For some nonlocal PDEs, its steady states can be seen as critical points of an associated energy functional. Therefore, if one can construct perturbations around a function such that the energy decreases to first order along the perturbation, this function cannot be a steady state. In this talk, I will discuss how this simple variational approach has led to some recent progresses in the following equations, where the key is to carefully construct a suitable perturbation. I will start with the aggregation-diffusion equation, which is a nonlocal PDE driven by two competing effects: nonlinear diffusion and long-range attraction. We show that all steady states are radially symmetric up to a translation (joint with Carrillo, Hittmeir and Volzone), and give some criteria on the uniqueness/non-uniqueness of steady states within the radial class (joint with Delgadino and Yan). I will also discuss the 2D Euler equation, where we aim to understand under what condition must a stationary/uniformly-rotating solution be radially symmetric. Using a variational approach, we settle some open questions on the radial symmetry of rotating patches, and also show that any smooth stationary solution with compactly supported and nonnegative vorticity must be radial (joint with Gómez-Serrano, Park and Shi).

Add to calendar :