Algebra/Number Theory/Combinatorics seminar

Algebraic subset sum problems over finite fields

Category

Speaker

Daqing Wan (UC Irvine)

Abstract

The subset sum problem over finite fields is a well known NP-complete problem, with a wide range of applications in coding theory, cryptography and computer science. In this talk, we will review this problem from both complexity and algorithm points of view. Then we propose a new algebraic variant, where many new interesting questions arise and some of them could be studied by methods from combinatorics and number theory.

Where

Millikan 2099, Pomona College

Misc. Information

Quantum plane, q-polynomial of rooted trees, and rooted graph invariants

Category

Speaker

Jozef Przytycki (George Washington University)

Abstract

We describe in this talk a new invariant of rooted trees and rooted graphs. We argue that the invariant is interesting on it own, and that it has connections to knot theory and homological algebra. However, the real reason that we propose this invariant to readers of is that we deal here with an elementary, interesting, new mathematics, and after this talk listeners can take part in developing the topic, inventing new results and connections to other disciplines of mathematics, and likely, statistical mechanics, and combinatorial biology.

Where

Millikan 2099, Pomona College

Misc. Information

Iterative methods for solving factorized linear systems

Category

Speaker

Anna Ma (CGU)

Abstract

Stochastic iterative algorithms such as the Kacmarz and Gauss-Seidel methods have gained recent attention because of their speed, simplicity, and the ability to approximately solve large-scale linear systems of equations without needing to access the entire matrix. In this work, we consider the setting where we wish to solve a linear system in a large matrix X that is stored in a factorized form, $X = UV$; this setting either arises naturally in many applications or may be imposed when working with large low-rank datasets for reasons of space required for storage. We propose a variant of the randomized Kaczmarz method for such systems that takes advantage of the factored form, and avoids computing $X$. We prove an exponential convergence rate and supplement our theoretical guarantees with experimental evidence demonstrating that the factored variant yields significant acceleration in convergence.

Where

Millikan 2099, Pomona College

Misc. Information

Biquasiles and dual graph diagrams

Category

Speaker

Sam Nelson (CMC)

Abstract

Dual graph diagrams are an alternative way to represent oriented knots and links in R^3 with connections to statistical mechanics. In this talk we will see a novel algebraic structure known as biquasiles and use finite biquasiles to distinguish knots and links in R^3 by counting biquasile colorings of dual graph diagrams.

Where

Millikan 2099, Pomona College

Misc. Information

Scheduling matches to allow shared transport, or how to get free tickets to your local team's home games

Category

Speaker

Christopher Tuffley (Massey University Manawatu)

Abstract

Consider a sports tournament with two divisions, in which each team is to play every other team in the same division, in a series of home and away games, one per week. Suppose moreover that every club with a team in division 1 also has a team in division 2, but not vice versa. If both teams from two clubs A and B play each other at the same venue in the same week, then the club with the away game will be able to arrange shared transport for its two teams; otherwise, separate transport arrangements will need to be made for each travelling team. How can we arrange the schedule to maximise the number of such "common fixtures"? In January 2011 the Manawatu Rugby Union approached me with an instance of this scheduling problem, in which there were 10 teams in division one and 12 in division two. They were so pleased with the schedule I provided that they gave me free tickets to the Manawatu Turbos' home games that year. I will explain how to solve this problem for the case of 2n teams in division one and 2n+2 in division two (joint work with Wayne Burrows), so that you, too, have an opportunity to benefit a local sports league, the environment, *and* yourself through combinatorics. The talk will be accessible to those without a background in combinatorics.

Where

Millikan 2099, Pomona College

Misc. Information

A sampling Kaczmarz-Motzkin algorithm for linear feasibility

Category

Speaker

Deanna Needell (CMC)

Abstract

We combine two iterative algorithms for solving large-scale systems of linear inequalities, the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz method. These methods employ certain sampling methods that project onto random faces of the solution polytope. We obtain a family of algorithms that generalize and extend both techniques. We prove several convergence results, and our computational experiments show our algorithms often outperform the original methods.

Where

Millikan 2099, Pomona College

Misc. Information

There will be a short organizational meeting just before this talk at 12:00 noon in the same room.

Combinatorics of diagrams of permutations

Category

Speaker

Alejandro Morales (UCLA)

Abstract

There are numerous combinatorial objects associated to a Grassmannian permutation w_\lambda that indexes cells of the totally nonnegative Grassmannian. We study several of these objects and their q-analogues in the case of permutations w that are not necessarily Grassmannian. We give two main results: first, we show that certain regions of an inversion arrangement, rook placements avoiding a diagram of w, and fillings of a diagram of w are equinumerous for all permutations w. Second, we give a q-analogue of these results by showing that the number of invertible matrices over a finite field avoiding a diagram of w is a polynomial in the size of the field, and for certain permutations a polynomial with nonnegative coefficients. This is joint work with Joel Lewis. The talk will be accessible to undergraduates familiar with discrete math.

Where

Millikan 2099, Pomona College

Misc. Information

Quadratic forms and graphs

Category

Speaker

Larry Gerstein (UCSB)

Abstract

Integral quadratic forms and graphs are both specified by symmetric matrices of integers. It is therefore reasonable to ask whether quadratic forms can tell us anything about graphs. We’ll explore this, with special attention to the graph isomorphism problem. The talk will be largely expository. In particular, no background in the theory of quadratic forms will be assumed.

Where

Millikan 2099, Pomona College

Misc. Information

A new generating function for counting zeroes of polynomials

Category

Speaker

Daniel Katz (Cal State Northridge)

Abstract

Suppose that we want to count the zeroes of a multivariable polynomial f whose coefficients come from the ring of integers modulo a power of a prime p. It is helpful to think of the polynomial f as having coefficients in the integers, and then can we count zeroes of f modulo each power of the prime p. The Igusa local zeta function Z_f is a generating function that organizes all these zero counts, and its poles tell us about the p-divisibility of the counts.

We devise a new method for calculating the Igusa local zeta function that involves a new kind of generating function G_f. Our new generating function is a projective limit of a family of generating functions, and contains more data than the Igusa local zeta function. The new generating function G_f resides in an algebra whose structure is naturally compatible with operations on the underlying polynomials, thus facilitating calculation of local zeta functions and helping us find zero counts of polynomials over finite fields and rings.

This is joint work with Raemeon A. Cowan and Lauren M. White.

Where

Millikan 2099 (Pomona College)

Misc. Information

On effective variations of Kronecker's approximation theorem

Category

Speaker

Lenny Fukshansky (CMC)

Abstract

The simplest version of the famous Kronecker's approximation theorem states that for a real number x the sequence of fractional parts of nx as n runs through natural numbers is dense in the interval [0,1) if and only if x is irrational. In this talk, I will discuss some generalizations and effective versions of this classical result.

Where

Millikan 2099, Pomona College

Misc. Information

Add to calendar
Syndicate content