Date/Time : 17 Jan 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Makoto Tatsuta, National Institute of Informatics, Japan

An inductive definition is a way to define a predicate by an expression which may contain the predicate itself. The predicate is interpreted by the least fixed point of the defining equation. Inductive definitions are important in computer science, since they can define useful recursive data structures such as lists and trees.  Inductive definitions are important also in mathematical logic, since they increase the proof theoretic strength. Martin-Lof’s system of inductive definitions given in 1971 is one of the most popular system of inductive definitions. In 2006 Brotherston proposed an alternative formalization of inductive definitions, called a cyclic proof system. In general, for proof search, a cyclic proof system can find an induction formula in a more efficient way than Martin-Lof’s system, since a cyclic proof system does not have to choose fixed induction formulas in advance. The equivalence of the provability of Martin-Lof’s system for inductive definitions and that of the cyclic proof system was conjectured in 2006. The speaker and Berardi solved it in 2017.

This talk will explain this problem.

Add to calendar :

Date/Time : 17 Jan 2024 16:00
Venue : S17 #06-11 (SR6)
Speaker : Tan Sheng Li, East China Normal University

Foliations are generalizations of fibrations on an algebraic surface. Some invariants of fibrations are generalized to foliations, e.g., Kodaira dimensions, geometric genus, Chern numbers, volume and slope. Fibrations with minimal slope must be hyperelliptic, which are double covers of ruled surfaces. We have no slope inequality for foliations, so it is interesting to construct some examples with small slopes. A nature way is to consider double covers of some transcendental foliations, we need to generalize the theory of double covers of fibrations to foliations. We will present an example whose slope is 12/7. This is a joint work with Jun LU and Shi XU.

Add to calendar :

Date/Time : 17 Jan 2024 15:00
Venue : S17 #04-06 (SR1)
Speaker : Yifeng Liu, IASM, Zhejiang University

BSD conjecture is one of the most influential problems in number theory, which concerns arithmetics of elliptic curves. It has been generalized to motives over number fields by Beilinson, Bloch and Kato in the 1980s. In this talk, we will survey recent progress of these conjectures for higher dimensional varieties.

Add to calendar :

Date/Time : 15 Jan 2024 15:00
Venue : S17 #04-06 (SR1)
Speaker : Liu Jialin, Alibaba Group (U.S.) Inc, Damo Academy

AI and data science have demonstrated remarkable promise in enhancing optimization algorithms. Utilizing AI/ML techniques, we aim to complement and potentially enhance traditional optimization methods, offering improvements in aspects like computational speed and solution quality. Despite these advancements, a deep, systematic understanding of these methods remains underdeveloped. In this talk, the speaker will demonstrate through concrete examples how mathematical tools, particularly optimization theory, can be used to unravel the mysteries of these ‘black boxes’. The speaker will also discuss the development of interpretable and reliable AI models for optimization, grounded in these mathematical principles.

Add to calendar :

Date/Time : 11 Jan 2024 17:00
Venue : S17 #04-05 (SR2)
Speaker : Yair Shenfeld, Brown University

It is classical that the ball is the unique shape which minimizes surface area for a given fixed volume. But what if we want to minimize surface area, where in addition to fixing the volume, we also fix the average width of the shape? This question turns out to be a very special case of long-standing conjectures at the heart of convex geometry. In the first part of the talk I will explain these conjectures and the significant progress that we made towards their resolutions. In the second part of the talk I will explain how these geometric problems can provide information on problems in combinatorics, which led us to the discovery of some surprising results in the theory of partially ordered sets.

Add to calendar :

Date/Time : 11 Jan 2024 16:00
Venue : S17 #05-12 (SR4)
Speaker : Mathias Weller, Technische Universität Berlin

In this talk, I will give a high-level introduction of some important computational problems in “Phylogenetics”, a branch of Biology that works with evolutionary histories of “taxa” (species, genes, samples, …). We will see some landmark results related to parameterized algorithms that analyze such histories.

In the second part of the talk, I would like to speak about a recently introduced layout-parameter for phylogenetic networks (basically rooted directed acyclic graphs with leaf-labels) called “scanwidth”, which has close ties to the treewidth of the underlying undirected graph. I will give examples for algorithmic results parameterized by the scanwidth and talk about efforts to efficiently compute the parameter itself.

Add to calendar :

Date/Time : 11 Jan 2024 10:00
Venue : via Zoom
Speaker : Shaoning Han, University of Southern California

Join Zoom Meeting
https://nus-sg.zoom.us/j/83242625129?pwd=ZmRzME93QndWbTNZQUdPUVdIS080Zz09

Meeting ID: 832 4262 5129
Passcode: 157423

Many regression problems arising in modern data science involve combinatorial decisions. For instance, sparsity is often introduced into statistical models to enhance interpretability and generalization. Outlier detection before training can contribute to model robustness. When cast as optimization problems, they are typically NP-hard, posing significant computational hurdles. To ease the computational burden, practitioners often either resort to much easier convex surrogates, albeit at the cost of sacrificing model fidelity, or rely on heuristics that lack theoretical guarantees unless stringent (sub)optimality conditions are met. This presentation provides insights into understanding and solving combinatorial regression problems through the lens of mixed-integer nonlinear programming. The first part focuses on developing convexification techniques that are applicable to general objectives with low-rank decompositions. In the second part, we explore solution methods tailored for a specific class of regression problems defined over graphs.

Add to calendar :

Date/Time : 10 Jan 2024 15:00
Venue : S17 #04-05 (SR2)
Speaker : Yu-Xiang Wang, University of California, Santa Barbara

Why do deep neural networks work better in practice than classical methods, e.g., kernels / splines? The talk covers a recent line of research that inspects DNNs from the classical non-parametric regression (or “curve fitting”) which reveals that the reason why DNNs work better might be due to its adaptivity when we tune its standard hyperparameters, which implicitly discovers hidden sparsity and low-dimensional structures. I will go over theory and examples to illustrate this point. For example, the effect of “Weight Decay” is in fact to select a small number of learned basis functions and the deeper the network is, the sparser it gets no matter how overparameterized the network is. Also, weight-decay helps a ConvResNeXT architecture to discover avoid the curse-of-dimensionality when the high-dimensional data is embedded in an unknown low-dimensional manifold. Last but not least, I will explain how the choice of “learning rate” determines the smoothness of functions that SGD can stably converge to, thus informing us on generalization.

References:
[1] Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive? https://arxiv.org/abs/2204.09664

[2] Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks. https://arxiv.org/abs/2307.01649

Add to calendar :

Date/Time : 09 Jan 2024 15:00
Venue : S17 #04-05 (SR2)
Speaker : Manlio Valenti, Swansea University

Ramsey’s theorem for n-tuples and k-colors can be generalized to colorings of binary trees. More precisely, TT^n_k states that given a k-coloring of the n-subsets of finite binary strings, there is a monochromatic set of strings that is isomorphic to the full binary tree. In the literature, this is sometimes referred to as
Chubb-Hirst-McNicholl tree theorem. In this talk, we will be focusing on the tree pigeonhole principle, namely the special case of the tree theorem for colorings of strings (i.e. n=1). We analyze its uniform computational content within the framework of Weihrauch reducibility. We show that different ways of phrasing the theorem yield different Weihrauch degrees. Our results provide new insights on the first-order part of the tree pigeonhole principle.

This is joint work with Damir Dzhafarov and Reed Solomon.

Add to calendar :