Friday, December 13, 2019 — 3:30 PM EST

Title: Permanent Hardness from Linear Optics

Speaker: Daniel Grier
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

One of the great accomplishments in complexity theory was Valiant's 1979 proof that the permanent of a matrix is #P-hard to compute.  Subsequent work simplified Valiant's ideas and even began to recast them as problems in quantum computing. 

Thursday, December 12, 2019 — 3:00 PM EST

Title: OutFn, M_gn and renormalized topological field theory

Speaker: Michael Borinsky
Affiliation: Nikhef
Room: MC 5417

Abstract:

I will report on recent joint work with Karen Vogtmann on the Euler characteristic of Out(F_n) and the moduli space of graphs.

Thursday, December 12, 2019 — 1:00 PM EST

Title: Graph covers with two new eigenvalues

Speaker: Olha Silina
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

I am going to talk about graph covers. If $Y$ is a cyclic cover of $X$, it turns out that $Y$ has the same spectrum as $X$ plus (possibly) some new eigenvalues. 

Friday, December 6, 2019 — 3:03 PM EST

Title: Biometric security: Design, implementation, and challenges

Speaker: Koray Karabina
Affiliation: Florida Atlantic University
Room: MC 5501

Abstract:

Biometric based cybersecurity technologies offer significant advantages in authentication, identification, and access control mechanisms.

Thursday, December 5, 2019 — 3:00 PM EST

Title: Inverses of Trees

Speaker: Krystal Guo
Affiliation: Centre de Recherches Mathématiques & Université de Montréal
Room: MC 5417

Abstract:

A tree is invertible if and only if it has a perfect matching.

Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix has entries in {0, ±1} and is the signed adjacency matrix of a graph which contains T.

Thursday, December 5, 2019 — 9:30 AM EST

Title: How can we optimize nonsmooth objectives globally?

Speaker: Andreas Griewank
Affiliation: Humboldt University, Germany
Room: MC 5501

Abstract:

In machine learning objective functions that are only piecewise smooth and should be globally minimized abound. The standard method of dealing with them is to apply a stochastic gradient method disregarding the rare points of nonsmoothness and hoping for the best as far as global optimality of the computed solution is concerned.

Friday, November 29, 2019 — 3:30 PM EST

Title: Incompressibility of classical distributions

Speaker: Debbie Leung
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

We prove a general, robust, single-letter lower bound on the achievable rate for ensembles of classical states, which holds even when Alice and Bob share free entanglement and allow a constant local error. 

Thursday, November 28, 2019 — 4:00 PM EST

Title: Resilience of the rank of random matrices

Speaker: Jorn van der Pol
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

I will discuss the preprint of this title by Ferber, Luh, and McKinley (arXiv:1910.03619).

Friday, November 22, 2019 — 3:30 PM EST

Title: Disjunctive Cuts through the V-Polyhedral Lens

Speaker: Aleksandr Kazachkov
Affiliation: Polytechnique Montréal
Room: MC 5501

Abstract:

Cutting planes, or cuts, are a critical component of modern integer programming solvers, but existing cuts implemented in solvers are relatively simple compared to those in the literature. We discuss the primary reasons for this disparity, as well as our recently-proposed V-polyhedral framework for mitigating some of these difficulties encountered by prior "stronger" cuts.

Friday, November 22, 2019 — 1:00 PM EST

Title: Submodular function maximization via the multilinear relaxation and contention resolution schemes

Speaker: Sharat Ibrahimpur
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

I will present a general framework for maximizing a nonnegative submodular set function $f$ subject to a variety of packing type constraints including multiple matroid constraints, knapsack constraints, and their intersections.

Thursday, November 21, 2019 — 4:00 PM EST

Title: Kummer's Theorem on binomial coefficients, etc.

Speaker: John Schanck
Affiliation: University of Waterloo
Room: MC 5501

Abstract: 

Some of us like the primes and call ourselves pure mathematicians. Some of us like the Catalan numbers and call ourselves combinatorialists.

Friday, November 15, 2019 — 3:30 PM EST

Title: The combinatorics of parametric Feynman integrals

Speaker: Marcel Golz
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

Feynman integrals are used in perturbative quantum field theory to compute the probabilities of processes involving elementary particles. They can be represented as Feynman graphs and exhibit a rich combinatorial structure. The parametric representation of Feynman integrals is particularly suitable to be studied from a combinatorial perspective since it contains well known objects like the Kirchhoff polynomial. 

Friday, November 15, 2019 — 1:00 PM EST

Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid

Speaker: Ben Moore
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

In 1978, it was shown that a natural greedy algorithm gives a 1/2 approximation to submodular maximization subject to a matroid constraint.

Thursday, November 14, 2019 — 4:00 PM EST

Title: Halfway to Rota's Basis Conjecture

Speaker: Shayla Redlin
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

Rota’s Basis Conjecture is that any rank-n matroid with n disjoint bases B_1, …, B_n has n disjoint transversal bases; a basis is transversal if it contains exactly one element from each B_i.

Thursday, November 14, 2019 — 3:00 PM EST

Title: From weakly separated collections to matroid subdivisions

Speaker: Nick Early
Affiliation: Perimeter Institute for Theoretical Physics
Room: MC 5417

Abstract:

We study arrangements of slightly skewed tropical hyperplanes, called blades, on the vertices of a hypersimplex $\Delta_{k,n}$.

Friday, November 8, 2019 — 3:30 PM EST

Title: Circuit-hyperplane relaxation and matroid representation

Speaker: Jim Geelen
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

Relaxing a circuit-hyperplane in a representable matroid can destroy representability.

Thursday, November 7, 2019 — 4:00 PM EST

Title: Counting Pentagons in Triangle-free Binary Matroids

Speaker: Adam Brown
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

Every triangle-free graph with n vertices contains at most (n/5)^5 cycles of length five, and this value is attained by the balanced blowup of the 5-cycle.

Thursday, November 7, 2019 — 3:00 PM EST

Title: Two-colouring hypersurface complements in open Richardson varities

Speaker: Kevin Purbhoo
Affiliation: University of Waterloo
Room: MC 5417

Abstract: 

Given an algebraic hypersurface $H \subset \mathbb{R}^n$, we can always 2-colour the components of the complement $\mathbb{R}^n \setminus H$ such that adjacent components are of opposite colours.

Thursday, November 7, 2019 — 1:00 PM EST

Title: Cospectral and strongly cospectral vertices

Speaker: Chris Godsil
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

If $a$ is a vertex in a graph with adjacency matrix $A$, the \textsl{walk module} generated by $a$ is the $A$-invariant subspace spanned by the vectors $A^re_a$, for $r\ge0$.

Friday, November 1, 2019 — 3:30 PM EDT

Title: A Quantum Query Complexity Trichotomy for Regular Languages

Speaker: Luke Schaeffer
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

We consider the quantum query complexity of regular languages and discover a surprising trichotomy: each regular language has query complexity either Theta(1), ~Theta(sqrt(n)) or Theta(n). 

Friday, November 1, 2019 — 1:00 PM EDT

Title: Maximizing non-monotone submodular functions

Speaker: Zishen Qu
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

Optimization of non-monotone submodular functions has applications in the maximum cut and maximum directed cut problems for graphs.

Thursday, October 31, 2019 — 4:00 PM EDT

Title: Edge-maximal graphs on surfaces

Speaker: James Davies
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

It is straightforward to show that, with the exception of small complete graphs, every edge-maximal planar graph triangulates the plane.

Thursday, October 31, 2019 — 3:00 PM EDT

Title: Interpolated versions of the Central Limit Theorem, and crossings of pair-partitions

Speaker: Alexandru Nica
Affiliation: University of Waterloo
Room: MC 5417

Abstract:

Thursday, October 31, 2019 — 1:00 PM EDT

Title: Perfect state transfer on Cayley graphs

Speaker: Soffia Arnadottir
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

Perfect state transfer on Cayley graphs

Wednesday, October 30, 2019 — 3:30 PM EDT

Title: Cutting a square into triangles of equal area

Speaker: Hayley Reid
Affiliation: University of Waterloo
Room:  MC 5501

Abstract:

Suppose you are given a square and asked to cut it into n triangles of equal area. If n is even the problem is almost trivial, but when n is odd the problem becomes much harder.

Pages

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2019 (168)
    1. December (6)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)