Wednesday, November 16, 2016
in Room 920 East Building, 1:102:10 pm (GRECS Seminar)
FirstOrder Definable Languages and CounterFree Automata
Presented by Pascal Weil, the Ada Peluso Visiting Professor, Hunter College; Research Professor, National Centre for Scientific Research, Université Bordeaux, France
Abstract:
We will discuss the deep connections between automata theory, formal language theory and logic. Regular languages (those that are accepted by finite state automata) are known to be exactly those specified by monadic second order logic (MSO). Firstorder logic is a very natural fragment of MSO: it is natural to ask whether that fragment is sufficient to specify regular languages (it isn’t!), and to characterize firstorder definable languages. The theorems of Schützenberger and McNaughtonPapert give a nice solution to this problem, with characterizations in terms of automata theory and in terms of regular expressions. It is however a third characterization, of an algebraic nature (it uses the notion of the syntactic monoid of a language: a finite, effectively computable monoid attached to a regular language), which provides the tools to effectively decide firstorder definability.
Quantifier alternation defines a natural hierarchy within first order logic, which yields an infinite hierarchy of within the class of firstorder definable languages. Investigating the decidability of this hierarchy is a challenging and active research area. Only a few of the lower levels of this hierarchy are known to be decidable.
Pascal Weil is a Research Professor of the highest rank in the National Centre for Scientific Research. Professor Weil received a Doctorate degree in Informatics from the University of Paris7 in 1985, a PhD in Mathematics from the University of Nebraska Lincoln in 1988, and a Habilitation Degree in Informatics from the University of Paris6 in 1989. He was director of LaBRI (Bordeaux Research Lab in Computer Science) from 2011 to 2015, as well as the Chair of the Scientific Council for Information Sciences (a national council within CNRS) from 2010 to 2014. Professor Weil has over 80 publications (including over 50 journal articles) focused on algebraic methods in computer science, notably in the field of automata and formal language theory and algorithmic and combinatorial problems in group theory.
Wednesday, October 19, 2016
in Room 922 East Building, 1:152:05 pm
The 2016 Nobel for the Economics of Contracts:
A Primer on Contract Design Modeling as a Problem of Statistical Inference with Applications in Financial Contracting
Presented by Jonathan Conning, Associate Professor, Department of Economics, Hunter College and the CUNY Graduate Center
Abstract:
The 2016 Nobel Prize in Economics has just been awarded to Oliver Hart and Bengt Holmstrom "for their contributions to contract theory." This talk will provide a short primer on some of the main modeling ideas in the field of field contract design under asymmetric information, with an emphasis on financial contracting under moral hazard. Holmstrom's (1979) paper on Moral Hazard and Observability and Grossman and Hart's (1983) paper An Analysis of the PrincipalAgent Problem established the modern "state space" approach to the problem which allowed the field to flourish and explode. In the canonical singletask moral hazard contracting problem a Principal (e.g. landowner, firm owner, investor) wishes to enter into a contract with an Agent (e.g. workercumtenant, employee, entreprenneur/borrower) to carry out a task or project whose stochastic outcome can be described by a statistical distribution which that can be shifted by the agent's choice of action (e.g. the agent's diligence or effort). When both the project's outcomes and the agent's action choices are both observable and contractible this is just a standard neoclassical problem (e.g. financial contracts with ArrowDebreu statecontingent commodities and standard asset pricing formulas). When the agent's actions are not observable the contract design problem becomes a statistical inference and constrained optimization problem: how to design a contract that ties the agent's renumeration to observable outcomes that strikes a balance between providing incentives for the agent to choose a right level of unobserved diligence/effort without imposing too much costly risk. After establishing a few key results of the canonical case the presentation moves on to study more challenging and interesting contracting situations from Holmstrom's work (and this author's own work) to study multitask and multiagent principal agent problems. I discuss questions such as the possible uses of relativeperformance evaluation (tournaments), whether to organize contracting directly through bilateral contracts or via specialized intermediaries of jointliability structures and other topics and show how the framework is helpful for analyzing key questions in modern corporate finance such as how firms borrow (via bonds, bank debt or equity), the design of microfinance contracts for the (collateral) poor, questions of regulation, the optimal size of banks and ownership structure of banks and much else.
Wednesday, September 28, 2016
in Room 920 East Building, 1:15 pm (GRECS Seminar)
Algebra in Automata Theory
Presented by Pascal Weil, the Ada Peluso Visiting Professor, Hunter College; Research Professor, National Centre for Scientific Research, Université Bordeaux, France
Abstract:
Automata and formal language theory are cornerstones of theoretical computer science with a strong mathematical flavor. The basic concepts include finite state automata and regular languages. Automata are a natural tool to represent and work on regular languages. Another important tool for specifying regular languages is provided by logic (first order and monadic second order). Logic is a great specification tool, but it does not have good algorithmic properties, and this is where algebra comes into play. With every finite state automaton, we can associate a finite algebraic structure, namely a monoid whose algebraic properties reflect the combinatorial or logical properties of the language accepted by the automaton. The fact that this socalled syntactic monoid is finite and effectively constructible gives us an elegant tool to effectively decide certain properties of regular languages.
Pascal Weil is a Research Professor of the highest rank in the National Centre for Scientific Research. Professor Weil received a Doctorate degree in Informatics from the University of Paris7 in 1985, a PhD in Mathematics from the University of Nebraska Lincoln in 1988, and a Habilitation Degree in Informatics from the University of Paris6 in 1989. He was director of LaBRI (Bordeaux Research Lab in Computer Science) from 2011 to 2015, as well as the Chair of the Scientific Council for Information Sciences (a national council within CNRS) from 2010 to 2014. Professor Weil has over 80 publications (including over 50 journal articles) focused on algebraic methods in computer science, notably in the field of automata and formal language theory and algorithmic and combinatorial problems in group theory.
Wednesday, April 20, 2016
in Room 920 East Building, 1:302:30 pm (GRECS Seminar)
Matrix Identities Involving Multiplication And Transposition
Presented by Mikhail Volkov, Ada Peluso Visiting Professor, Hunter College; Professor of Mathematics, Ural Federal University, Russia
Abstract:
Matrices and matrix operations constitute basic tools for algebra, analysis and many other parts of mathematics. Important properties of matrix operations are often expressed in form of laws or identities such as the associative law for multiplication of matrices. Studying matrix identities that involve multiplication and addition is a classic research direction motivated by several important problems in geometry and algebra. Matrix identities involving along with multiplication and addition also certain involution operations (such as taking the usual or symplectic transpose of a matrix) have attracted much attention as well.
If one aims to classify matrix identities of a certain type, then a natural approach is to look for a collection of "basic" identities such that all other identities would follow from these basic identities. Such a collection is usually referred to as a basis. For instance, all identities of matrices over an infinite field involving multiplication only are known to follow from the associative law. Thus, the associative law forms a basis of such "multiplicative" identities. For identities of matrices over a finite field or a field of characteristic 0 involving both multiplication and addition, the powerful results by Kruse–L'vov and Kemer ensure the existence of a finite basis. In contrast, multiplicative identities of matrices over a finite field admit no finite basis.
Here we consider matrix identities involving multiplication and one or two natural oneplace operations such as taking various transposes or Moore–Penrose inversion. Our results may be summarized as follows.
None of the following sets of matrix identities admits a finite basis:
• the identities of n×nmatrices over a finite field involving multiplication and usual transposition;
• the identities of 2n×2nmatrices over a finite field involving multiplication and symplectic transposition;
• the identities of 2×2matrices over the field of complex numbers involving either multiplication and Moore–Penrose inversion or multiplication, Moore–Penrose inversion and Hermitian conjugation;
Wednesday, February 24, 2016
in Room 920 East Building, 1:002:00 pm (GRECS Seminar)
Road Coloring Theorem
Presented by Mikhail Volkov, Ada Peluso Visiting Professor, Hunter College; Professor of Mathematics, Ural Federal University, Russia
Abstract:
I shall present a recent advance in the theory of finite automata: Avraam Trahtman's proof of the socalled Road Coloring Conjecture by Adler, Goodwyn, and Weiss; the conjecture that admits a formulation in terms of recreational mathematics arose in symbolic dynamics and has important implications in coding theory. The proof is elementary in its essence but clever and enjoyable.
Wednesday, February 17, 2016
in Room 920 East Building, 1:002:00 pm (Departmental
Lecture Series)
Synchronizing finite automata: a problem everyone can understand but nobody can solve (so far)
Presented by Mikhail Volkov, Ada Peluso Visiting Professor, Hunter College; Professor of Mathematics, Ural Federal University, Russia
Abstract:
Most current mathematical research, since the 60s, is devoted to fancy situations: it brings solutions which nobody understands to questions nobody asked” (quoted from Bernard Beauzamy, "Real Life Mathematics", Irish Math. Soc. Bull. 48 (2002), 4346). This provocative claim is certainly exaggerated but it does reflect a really serious problem: a communication barrier between mathematics (and exact science in general) and human common sense. The barrier results in a paradox: while the achievements of modern mathematics are widely used in many crucial aspects of everyday life, people tend to believe that today mathematicians do "abstract nonsense" of no use at all. In most cases it is indeed very difficult to explain to a nonmathematician what mathematicians work with and how their results can be applied in practice. Fortunately, there are some lucky exceptions, and one of them has been chosen as the present talk's topic. It is devoted to a mathematical problem that was frequently asked by both theoreticians and practitioners in many areas of science and engineering. The problem, usually referred to as the synchronization problem, can be roughly described as the task of determining the simplest way to restore control over a device whose current state is not known:– think of a satellite which loops around the Moon and cannot be controlled from the Earth while "behind" the Moon. While easy to understand and practically important, the synchronization problem turns out to be surprisingly hard to solve even for finite automata that constitute the simplest mathematical model of realworld devices. This combination of transparency, usefulness and unexpected hardness should, hopefully, make the talk interesting for a wide audience.
Professor Volkov will also give a semester course on synchronizing automata (Synchronizing Finite Automata: Math 795.64. Th, 7:359:25 pm, Room 921 East). The course is basically selfcontained as it requires almost no prerequisites; in particular, no prior knowledge of automata theory is assumed. The course contains a detailed overview of the current stateoftheart in the theory of synchronizing automata and quickly leads to some recent advances of the theory and a number of tantalizing open problems.
Special Year in Hyperbolic Geometry
Hunter College, City University of New York, Room 920 East Building, Fall 2014Spring 2015
The research theme for the academic year 20142015 will be the subject of hyperbolic geometry and its many related areas. The year will feature a series of lectures, an ongoing seminar, and several visitors. During this period the Ada Peluso Visiting Professors will be
• Athanase Papadopoulos of the Universite de Strasbourg (Fall 2014).
• Hugo Parlier of the University of Fribourg, Switzerland (Spring 2015).
The first two seminars will be given by Ara Basmajian and the next four by Athanase Papadopoulos. For the latest information about the seminar and abstracts for the talks go to the website: http://wfs.gc.cuny.edu/CArettines/hypgeo/index.html
The Schedule
October 1, 2014 A Crash Course on Hyperbolic Surfaces I
October 8 A Crash Course on Hyperbolic Surfaces II
October 15 On Funk Geometry
October 22 Hilbert Problem No. IV
October 29 Spherical and Hyperbolic Geometry
November 5 Spherical and Hyperbolic Trigonometry
November 12 Filling Curves on Hyperbolic Surfaces
November 19 Angles of Intersection on the Punctured Torus
November 26 The Work of Maryam Mirzahani
February 4, 2015 Pants and Infinite Type Surfaces
February 11 Combinatorial Moduli Spaces
February 18 no meeting
February 25 Systolic Inequalities and Kissing Numbers for Surfaces
March 4 presenter, Federica Fanoni (University of Fribourg)
March 11 Chromatic Numbers for Hyperbolic Surfaces
March 18 presenter, Julien Paupert (Arizona State University)
March 25 presenter, Bram Petri (University of Fribourg)
April 1 Curve Graphs, Pants Graphs and Flip Graphs of Surfaces
April 8 no meeting, Spring Break
April 15 no meeting, MSRI Workshop
April 22 no meeting, Identities Workshop
April 29 Puzzles, Triangulations and Moduli Spaces  by Hugo Parlier,
Ada Peluso Visiting Professor, Hunter College; Professor, University of Fribourg
CONTACT: Contact Ara Basmajian (abasmajian@gc.cuny.edu) for further information or questions regarding this special year.
VISITORS: Enter by way of the Hunter West building, located on the southwest corner of Lexington Avenue and 68th Street. After going through security, go up to the 3rd floor and walk across the bridge to the East Building. Take the elevator to the 9th floor, Room 921.
Tuesday, March 12, 2013 in Room 714 West Building, 5:30 pm. (Fourth Distinguished Undergraduate RTG Lecture in Number Theory, a Joint Project of Columbia University, CUNY, and New York University)
Taxicabs and the Sum of Two Cubes
Presented by Joseph H. Silverman
Abstract:
Some numbers, such as 9=1^{3}+2^{3} and 370=3^{3}+7^{3}, can be written as the sum of two cubes. Are there numbers that can be written as the sum of cubes in two (or more) essentially different ways? This elementary question will lead us into beautiful areas of mathematics where number theory, geometry, algebra, calculus, and even internet security interact in surprising ways.
Wednesday, November 7, 2012 in Room 920 East Building, 1:103:00 pm. Lunch and refreshments served following the talk. (Soup and Science Series)
A Knot's Tale For Halloween
Presented by Tatyana Khodorovskiy, Assistant Professor of Mathematics,
Hunter College of the City University of New York.
Abstract:
Knots have appeared many times in human history, from marine knots to Celtic knots to our own knotted up DNA! As a mathematical subject, knot theory began in 1867, when Lord Kelvin was working on creating the periodic table of elements. He proposed that the different chemical properties of atoms can be described by the different ways their tubes of ether are knotted up. He and physicist Peter Tait went on to compose the first table of knots. Well, this particular connection didn’t really pan out so well... Today, however, knot theory is an indispensable part of a field of math called topology. In this talk, I will define what knots are and discuss their role in life and math.
Wednesday, October 24, 2012
in Room 920 East Building, 1:302:30 pm, preceded by a Tea at 1:00 pm (Departmental
Lecture Series)
Overgroup Lattices in Finite Groups
Presented by Levi Biock, BA/MA student in Mathematics,
Hunter College of the City University of New York.
Abstract:
To answer the PalfyPudlak Question, John Shareshian conjectured that a certain class, Dd, of lattices are not overgroup lattices in any finite group. To prove this conjecture one needs to know the structure of a group G and the embedding of a subgroup H in G, such that there are only two maximal overgroups of H in G and H is maximal in both. Towards a proof of this conjecture, we consider the minimal normal subgroups of G and use these minimal normal subgroups to determine the structure of G and determine the embedding of H in G.
This work was carried out at SURF 2012, California Institute of Technology, mentor: Michael Aschbacher.
Wednesday, March 7, 2012
in 224 East Building, 1:102:30 pm (Soup and Science Series)
Using Geometry To Classify Surfaces
Presented by Ara Basmajian, Professor of Mathematics,
Hunter College and the Graduate Center of the City University of New York.
Abstract:
We will begin with the question: What properties do the surface of a basketball
and the surface of a football share? In what sense are they the same?
In what sense are they different? This discussion will lead naturally
to the notion of a surface (a two dimensional space). Next, we introduce
the three basic geometries (euclidean, spherical, hyperbolic) and their
properties. Hyperbolic geometry, though the least known of the three,
plays a prominent, fundamental role in our understanding of surfaces and
the geometries they admit. In fact, we will see thet most surfaces admit
a hyperbolic geometry. We will finish by mentioning some recent work on
three dimensional spaces.
