Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Select All
Limit to events tagged with one or more of:
Select All
Limit to events where the audience is one or more of:
Select All
Friday, February 28, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Xiao Hu

Title:What is New in Join-Aggregate Query Processing?

Speaker: Xiao Hu
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Join-aggregate queries defined over commutative semirings subsume a wide variety of common algorithmic problems, such as graph pattern matching, graph colorability, matrix multiplication, and constraint satisfaction problems. Developing efficient algorithms for computing join-aggregate queries in the conventional RAM model has been a holy grail in database theory. One of the most celebrated results in this area is the Yannakakis algorithm dating back to 1981. Despite its prominence as a textbook solution, no improvements in its complexity have been made over the past 40 years. In this talk, I will present the first algorithm that improves upon Yannakakis for computing acyclic join-aggregate queries. Moreover, this algorithm is proven to be output-optimal among all combinatorial algorithms. One application is an output-optimal algorithm for chain matrix multiplication over sparse matrices. Beyond combinatorial algorithms, I will also show how fast matrix multiplication can further speed up the processing of conjunctive queries, a critical subclass of join-aggregate queries. Finally, I will highlight a few interesting open problems in this area.

 

 

Monday, March 3, 2025 11:30 am - 12:30 pm EST (GMT -05:00)

Algebraic Graph Theory-Theo McKenzie

Title: Precise Eigenvalue Location for Random Regular Graphs

Speaker: Theo McKenzie
Affiliation: Stanford University
Location: Please contact Sabrina Lato for Zoom link.

Abstract:The spectral theory of regular graphs has broad applications in theoretical computer science, statistical physics, and other areas of mathematics. Graphs with optimally large spectral gap are known as Ramanujan graphs. Previous constructions of Ramanujan graphs are based on number theory and have specific constraints on the degree and number of vertices. In this talk, we show that, in fact, most regular graphs are Ramanujan; specifically, a randomly selected regular graph has a probability of 69% of being Ramanujan. We establish this through a rigorous analysis of the Green’s function of the adjacency operator, focusing on its behavior under random edge switches.

Monday, March 3, 2025 3:00 pm - 4:00 pm EST (GMT -05:00)

Tutte colloquium-Peter Nelson

Title:Two-coloured lines in finite geometry

Speaker: Peter Nelson
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Given a colouring of the points of a projective plane, when is it true that every line contains at most two colours? I will discuss recent generalizations of classical results in this area, and a surprising link with a famous question in graph theory.

 

 

Thursday, March 6, 2025 2:00 pm - 3:00 pm EST (GMT -05:00)

Algebraic and enumerative combinatorics seminar-Andrew Sack

Title: Operahedron Lattices

Speaker Andrew Sack
Affiliation University of Michigan
Location MC 5479

 Abstract: Two classical lattices are the Tamari lattice on bracketings of a word and the weak order on permutations. The Hasse diagram of each of these lattices is the oriented 1-skeleton of a polytope, theassociahedron and the permutohedron respectively. We examine a poset on bracketings of rooted trees whose Hasse diagram is the oriented 1-skeleton of a polytope called th operahedron. We show this poset is a lattice which answers question of Laplante-Anfossi. These lattices provide an extremelynatural generalization of both the Tamari lattice and the weak order.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Friday, March 7, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Yuen-Man Pun

Title:What is New in Join-Aggregate Query Processing?

Speaker: Yuen-Man Pun
Affiliation: Australian National University
Location: MC 5501

Abstract: : In this talk, we will address the maximum-likelihood (ML) formulation and a least-squares (LS) formulation of the time-of-arrival (TOA)-based source localization problem. Although both formulations are generally non-convex, we will show that they both possess benign optimization landscape. First, we consider the ML formulation of the TOA-based source localization problem. Under standard assumptions on the TOA measurement model, we will show a bound on the distance between an optimal solution and the true target position and establish the local strong convexity of the ML function at its global minima. Second, we consider the LS formulation of the TOA-based source localization problem. We will show that the LS formulation is globally strongly convex under certain condition on the geometric configuration of the anchors and the source and on the measurement noise. We will then derive a characterization of the critical points of the LS formulation, which leads to a bound on the maximum number of critical points under a very mild assumption on the measurement noise and a sufficient condition for the critical points of the LS formulation to be isolated. The said characterization also leads to an algorithm that can find a global optimum of the LS formulation by searching through all critical points. Lastly, we will discuss some possible future directions.