Algebra/Number Theory/Combinatorics seminar

Formal groups -- a finite history

Category

Speaker

Ghassan Sarkis (Pomona College)

Abstract

A formal group is a power series that behaves like a group law and exhibits deep connections to number theoretic results from reciprocity laws to elliptic curves, and from local class field theory to dynamical systems. In this talk, I will introduce formal groups, describe their more salient features, and trace some of their unexpected cameos since (and sometimes before) their invention/discovery more than 70 years ago, ending with an answer to a recent question from the internet (and Jonathan Lubin).

Where

Millikan 2099, Pomona College

Misc. Information

TBA

Category

Speaker

Alex Hof (Pomona College)

Abstract

TBA

Where

Millikan 2099, Pomona College

Misc. Information

TBA

Category

Speaker

Mike Orrison (HMC)

Abstract

TBA

Where

Millikan 2099, Pomona College

Misc. Information

TBA

Category

Speaker

Stephan Garcia (Pomona College)

Abstract

TBA

Where

Millikan 2099, Pomona College

Misc. Information

An algebraic perspective on integer sparse recovery

Category

Speaker

Lenny Fukshansky (CMC)

Abstract

A basic problem of compressed sensing is that of sparse recovery: accurately reconstruct a sparse signal x in R^d from its noisy measurement Ax+e in R^m, where m < d, A is an m x d compression matrix, and e is an error vector. The signal x is called s-sparse if it has only s nonzero coordinates, where s is usually no bigger than m. There are known recovery algorithms for the situations when m = O(s lod (d)), which usually rely on incoherence or restricted isometry properties of the matrix A. In this talk, we will discuss an approach to this problem when the sparse signal vector x is assumed to have integer coordinates, a direction with many potential applications in digital communications and related fields. We will outline a number-theoretic construction of matrices A that allow for efficient recovery over noisy channels. We will also talk about some limitations of this approach. This is joint work with Deanna Needell and Benny Sudakov.

Where

Millikan 2099, Pomona College

Misc. Information

A new way to view popping algorithms

Category

Speaker

Mark Huber (CMC)

Abstract

One method of sampling from high dimensional distributions is called "popping", and was first introduced by David Wilson in 1996. In this talk I'll show how these popping algorithms arise naturally as a special case of a type of acceptance rejection algorithm. In particular, I'll describe how the algorithm for generating uniformly from the rooted directed spanning trees of a graph, and for generating uniformly from sink free orientations of a graph, both come about from such an analysis. I'll then talk about how these algorithms can be used to generate perfectly from problems where popping does not apply such as the isolated (aka independent) sets of a graph.

Where

Millikan 2099, Pomona College

Misc. Information

Psyquandles, singular knots and pseudoknots

Category

Speaker

Sam Nelson (CMC)

Abstract

Singular knots are 4-valent spatial graphs considered up to rigid vertex isotopy. Pseudoknots are knots with some precrossings, classical crossings where we don't know which strand is on top. Psyquandles are a new algebraic structure which defines invariants of both singular and pseudoknots. In particular we will define the Jablan Polynomial, a generalization of the Alexander polynomial for singular/pseudoknots arising from psyquandles. This is joint work with Natsumi Oyamaguchi (Shumei University) and Radmila Sazdanovic (NCSU).

Where

Millikan 2099, Pomona College

Misc. Information

Random numerical semigroups

Category

Speaker

Chris O'Neill (UC Davis)

Abstract

A numerical semigroup is a subset of the natural numbers that is closed under addition. Consider a numerical semigroup S selected via the following random process: fix a probability p and a positive integer M, and select a generating set for S from the integers 1,...,M where each potential generator has probability p of being selected. What properties can we expect the numerical semigroup S to have? For instance, when do we expect S to contain all but finitely many positive integers, and how many minimal generators do we expect S to have? In this talk, we answer several such questions, and describe some surprisingly deep combinatorial structures that naturally arise in the process. No familiarity with numerical semigroups or probability will be assumed for this talk.

Where

Millikan 2099, Pomona College

Misc. Information

TBA

Category

Speaker

Achill Schürmann (University of Rostock and CMC)

Abstract

TBA

Where

Millikan 2099, Pomona College

Misc. Information

The complexities of integer points in polytopes

Category

Speaker

Danny Nguyen (UCLA)

Abstract

The structure of integer points in polytopes is of interest both in Combinatorics and Integer Programming. Given a polytope in fixed dimension, the works of Lenstra (1983) and Barvinok (1993) showed that finding and counting integer points can be solved in polynomial time. This led to a series of subsequent developments by Kannan, Barvinok, Woods and others, generalizing these results to various operations on polytopes (union, projection, etc.). An important generalization of these problems asks for satisfiability of formulas in Presburger arithmetic. We show that there are sharp limits on any positive results in the generalized setting. Notably, we prove that satisfiability of with three quantifiers in dimension 5 is NP-complete. In the first half of the talk we give a broad overview the subject. We state the results, explain the tools that were used, and how the new results fit the existing literature. In the second half of the talk, we will outline the proof of the main complexity result, which employs working with continued fractions and arithmetic progressions. The talk will be self contained and assume no prior knowledge of the subject.

Where

Millikan 2099, Pomona College

Misc. Information

Add to calendar
Syndicate content