Date/Time : 05 Apr 2023 17:00
Venue : S17 #05-11 (SR5)
Speaker : Frank Stephan, National University of Singapore

Languages over the unary alphabet have been studied in computer science for a long time. The present work investigates regular languages over the unary alphabet and one investigates the various forms of representing them by finite automata. Here three types of automata are studied:

(a) Deterministic finite automata where the finite automaton has exactly one run per word which is accepting iff the word is in the given language.

(b) Nondeterministic finite automata where there are choices in the states on how to procede with a run on various symbols, a word is in the language iff there is some run which is accepting.

(c) Unambiguous finite automata which are a special case of nondeterministic finite automata and which either reject a word or which have exactly one accepting run for a word.

The results presented are from the following two areas:

(1) This paper improves the upper bound of the equality problem of unary nondeterministic automata from an exponential in the second root to an exponential in the third root of the number of states. This almost matches a known lower bound based on the exponential time hypothesis by Fernau and Krebs.

(2) It is established that the standard regular operations of union, intersection, complementation and Kleene star cause either only a polynomial or a quasipolynomial blow-up.
Concatenation of two n-state ufas, in worst case, causes a blow-up from n to a function with an exponent of sixth root of n. Decision problems of finite formulas using regular operations and comparing languages given by n-state unambiguous automata, in worst case, require an exponential-type of time under the Exponential Time hypothesis and this complexity goes down to quasipolynomial time in the case that the concatenation of languages is not used in the formula. Merely comparing two languages given by n-state ufas in Chrobak Normal Form is in LOGSPACE.

This talk is joint work with Gordon Hoi, Sanjay Jain and Christopher Tan.

Add to calendar :

Date/Time : 05 Apr 2023 16:00
Venue : via Zoom
Speaker : Noam Lifshitz, Hebrew University

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

Meeting ID: 810 4646 2775
Passcode: 23571113

A subset A of a group is said to be product free if for all elements a, b in A their product ab is not in A. In 1985 Babai and Sos posed the problem of determining the largest product free sets in the alternating group. We solve this problem completely when n is sufficiently large.

Our proof combines representation theory with a recent machinery we developed called `hypercontractvity for global functions’.

Based on joint works with Keevash, Long, and Minzer.

Add to calendar :

Date/Time : 04 Apr 2023 16:00
Venue : via Zoom
Speaker : Johannes Flake, MPIM Bonn

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

Meeting ID: 864 4631 5086
Passcode: 280937

I will explain a construction of categories with a tensor product using topological operations involving manifolds, or more precisely, cobordisms. Then I will show how to analyze categories like these using algebraic and representation-theoretic ideas. The categories in question include Deligne’s interpolation categories and Khovanov-Sazdanovic’s cobordism categories. We will discuss their Grothendieck rings and, if time permits, their monoidal centers.

Add to calendar :

Date/Time : 03 Apr 2023 16:00
Venue : S17 #04-06 (SR1)
Speaker : Xuhua He, Chinese University of Hong Kong

An invertible matrix is called totally positive if all its minors are positive. In 1994, Lusztig developed the theory of total positivity for arbitrary split real reductive groups and their flag manifolds. He further generalized the theory to arbitrary Kac-Moody groups in 2019. The theory of total positivity has found important applications in different areas: cluster algebras, higher Teichmuller theory, the theory of amplituhedron in physics, etc.

In this talk, we will discuss some remarkable combinatorial, geometric and representation-theoretic aspects of total positivity. This talk is based on some recent works with Huanchen Bao.

Add to calendar :

Date/Time : 30 Mar 2023 11:00
Venue : S17 #05-12 (SR4)
Speaker : Song Jinfeng, National University of Singapore

Let G be a reductive group over an algebraically closed field with positive characteristic, and N be the unipotent radical of a Borel subgroup. The quantum Frobenius splitting introduced by Lusztig gives an algebraic construction for a Frobenius splitting of the unipotent group N. Another important construction on N is the cluster algebra structure established by Geiss-Leclerc-Schroer. In this talk, I will explain that the algebraic Frobenius splitting on N is compatible with its cluster structure. This is based on an ongoing work.

Add to calendar :

Date/Time : 30 Mar 2023 10:00
Venue : via Zoom
Speaker : Xun Huan, University of Michigan

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

Meeting ID: 977 560 6531
Passcode: 123321

Experiments are indispensable for learning and developing models in engineering and science. A careful design of these often-expensive data-acquisition opportunities can be immensely beneficial. Simulation-based optimal experimental design, while leveraging a predictive model, offers a framework to systematically quantify and maximize the value of experiments. We focus on designing a finite sequence of experiments, seeking optimal design policies that can (a) adapt to newly collected data during the sequence (i.e. feedback) and (b) anticipate future changes (i.e. lookahead). We cast this sequential decision-making problem in a Bayesian setting with information-based utilities, and solve it numerically via policy gradient methods from reinforcement learning. In particular, we directly parameterize the policies and value functions by neural networks—thus adopting an actor-critic approach—and improve them using gradient estimates produced from simulated design and observation sequences. We demonstrate the overall method on a problem of optimal sensor movement for contaminant source inversion.

Add to calendar :

Date/Time : 30 Mar 2023 16:00
Venue : S17 #04-06 (SR1)
Speaker : Simon Eberle, Basque Center for Applied Mathematics, Spain

We will investigate an old problem posed by Isaac Newton on shapes that do not admit gravity in the cavity. We will see that it can be equivalently formulated as a question on the rigidity of global solutions of the obstacle problem, a question that recently has been answered in full generality.

This is joint work with A. Figalli, H. Shahgholian and G. S. Weiss.

Add to calendar :

Date/Time : 29 Mar 2023 16:00
Venue : via Zoom
Speaker : Xizhi Liu, University of Warick

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

Meeting ID: 810 4646 2775
Passcode: 23571113

We present a general approach for determining the maximum number of edges in an n-vertex r-uniform hypergraph that does not contain t+1 vertex-disjoint copies of F, when n is large, t = o(n), and F is nondegenerate. This extends old results of Simonovits and Moon on complete graphs.

Based on joint work with Jianfeng Hou, Heng Li, Long-Tu Yuan, and Yixiao Zhang.

Add to calendar :

Date/Time : 29 Mar 2023 17:00
Venue : S17 #05-12 (SR4)
Speaker : Ruofei Xie,

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

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

In the article “Highness Properties Close to PA-Completeness”, Greenberg, Miller, and Nies left the following questions:

–Is there a finite collection of functionals {Gamma_i:i<N} such that for every martingale M majorizing the optimal c.e. supermartingale m, Gamma_i(M) is a DNC_k function for some i<N?

–Is there a uniform way to compute a DNC_k function from a martingale M majorizing m whose initial capital is bounded by 1?

In the talk, I will try to answer these questions.

Add to calendar :