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, January 17, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Stephan Pfannerer-Mittas

Title:A mystery group action and the mystery statistic

Speaker: Stephan Pfannerer-Mittas
Affiliation: University of Waterloo
Location: MC 5501

Abstract: In 2010, B. Rhoades proved that promotion on rectangular standard Young tableaux together with the associated fake-degree polynomial shifted by an appropriate power, provides an instance of the cyclic sieving phenomenon. 

Motivated in part by this result, we show that we can expect a cyclic sieving phenomenon for m-tuples of standard Young tableaux of the same shape and the m-th power of the associated fake-degree polynomial, for fixed m, under mild and easily checked conditions. However, we are unable to exhibit an appropriate group action explicitly.
Put differently, we determine in which cases the mth tensor power of a character of the symmetric group carries a permutation representation of the cyclic group. 
To do so, we use a method proposed by N. Amini and P. Alexandersson, which amounts to establishing a bound on the number of border-strip tableaux. 

Finally, we apply our results to the invariant theory of tensor powers of the adjoint representation of the general linear group. In particular, we prove the existence of a statistic on permutations, which is equidistributed with the RSK-shape and invariant under rotation.

This is based on joint work with Per Alexandersson, Martin Rubey and Joakim Uhlin.

 

 

Friday, January 24, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Jim Geelen

Title: Well-quasi-ordering and connectivity

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

Abstract: Connectivity systems provide an abstract framework for studying various connectivity notions on graphs, matroids, and other combinatorial structures. In joint work with Rutger Campbell, we prove a novel well-quasi-ordering result on certain connectivity systems which gives new excluded minor results in matroid theory and gives new proofs for several results in graph theory.

 

 

Friday, January 31, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Jane Gao

Title:Evolution of random graph orders and their dimensions

Speaker: Jane Gao
Affiliation: University of Waterloo
Location: MC 5501

Abstract: A poset is a set X equipped with a partial order. In this talk I will briefly review the literature of different models on random orders. Then we discuss a particular model called the random graph order. The random graph order is classical model to generate a random causal set, which was introduced in physics to model and analyse the space-time universe. 

We will focus on an open problem proposed by Erdos, Kierstad and Trotter on the evolution of the dimensions of random graph orders. This problem has been studied by Albert and Frieze, and by Erdos, Kierstad and Trotter around 1990. Better bounds on the dimensions were obtained by Bollobas and Brightwell in 1997, for “non-sparse” random graph orders. We study the last piece of the puzzle, in the bipartite case, by investigating “a transition phase” that was predicted to occur in the sparse regime by Bollobas and Brightwel, and we prove a negative result to their prediction. We expect that a similar phenomenon would occur in the nonbipartite case.

This talk is based on a collaborated work with Arnav Kumar. 

 

 

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

Tutte colloquium-Levent Tuncel

Title: A New Complexity Analysis of Primal-Dual Interior-Point Methods with Applications to Hyperbolic Cone Programming

Speaker: Levent Tuncel
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Primal-dual interior-point methods stand at the forefront of convex optimization, distinguished by their theoretical efficiency and practical robustness. After presenting the fundamental 
structure of these algorithms, I will introduce a complexity measure for a large family of primal-dual algorithms. A consequence of the new analyses of this complexity measure is a substantial improvement of the iteration 
complexity bounds for these primal-dual algorithms on hyperbolic cone programming problems.

This talk is based on joint work with Joachim Dahl and Lieven Vandenberghe.

 

 

Friday, February 14, 2025 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte colloquium-Xi He

Title:Accuracy Aware Minimally Invasive Data Exploration For Decision Support

Speaker: Xi He
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Decision-support (DS) applications, crucial for timely and informed decision-making, often analyze sensitive data, raising significant privacy concerns. While privacy-preserving randomized mechanisms can mitigate these concerns, they introduce the risk of both false positives and false negatives. Critically, in DS applications, the number of false negatives often needs to be strictly controlled. Existing privacy-preserving techniques like differential privacy, even when adapted, struggle to meet this requirement without substantial privacy leakage, particularly when data distributions are skewed. This talk introduces a novel approach to minimally invasive data exploration for decision support. Our method minimizes privacy loss while guaranteeing a bound on false negatives by dynamically adapting privacy levels based on the underlying data distribution. We further extend this approach to handle complex DS queries, which may involve multiple conditions on diverse aggregate statistics combined through logical disjunction and conjunction. Specifically, we define complex DS queries and their associated accuracy requirements, and present algorithms that strategically allocate a privacy budget to minimize overall privacy loss while satisfying the bounded accuracy guarantee.

 

 

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.