Seminar • Algorithms and Complexity • The Brascamp-Lieb Polytope: Matroid Matching and Rank of Matrix Spaces

Friday, October 21, 2022 — 1:00 PM to 2:00 PM EDT

Please note: This seminar will take place in DC 1304 and online.

Akshay Ramachandran, Postdoctoral Researcher
University of Amsterdam and Centrum Wiskunde & Informatica

Given a linear subspace of matrices $\mathcal{A} := \langle A_{1}, …, A_{m} \rangle \subseteq \mathbb{F}^{n \times n}$, Edmond’s problem asks to decide whether there is a matrix in $\mathcal{A}$ of full rank. This can be rephrased as finding the rank of the matrix $A := \sum_{i=1}^{m} x_{i} A_{i}$ over the field of rational functions $\mathbb{F}(x_{1}, …, x_{m})$. This linear algebraic problem turns out to connect to various problems in combinatorial optimization: maximum matching in graphs, linear matroid intersection, and their common generalization linear matroid matching [Lovasz, 1980].

By the Schwarz-Zippel lemma, there is a simple randomized algorithm to answer this question, but derandomizing this result is a major open question that would be an important breakthrough in complexity theory [KI04].

A related variant, known as the non-commutative Edmond’s problem, asks to compute the rank of $A$ over the “free skew field” in which the variables $x$ no longer commute. Surprisingly, recent work has shown that this seemingly more complicated problem can in fact be solved by a deterministic algorithm in polynomial time.

In this talk, we will discuss one of these algorithms and a recent result [Oki, Soma] relating this problem to the Brascamp-Lieb Theorem from functional analysis. In particular, they show that the algorithm for non-commutative rank can be used to optimize over the Brascamp-Lieb polytope for rank 2 instances, which gives the first truly polynomial time algorithm to maximize the fractional relaxation of linear matroid matching [GP08]. This problem can be considered as a natural “higher rank” generalization of optimization over linear matroid polytopes.

To join this seminar on Zoom, please go to https://uwaterloo.zoom.us/j/91061677783. You can also attend in person in DC 1304.

Location
DC - William G. Davis Computer Research Centre
DC 1304 | Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Event tags

July 2024

S M T W T F S
30
1
6
7
9
10
11
12
13
14
15
17
20
21
23
27
28
29
30
1
2
3
1. 2024 (182)
1. September (1)
2. August (4)
3. July (19)
4. June (17)
5. May (23)
6. April (41)
7. March (27)
8. February (25)
9. January (25)
2. 2023 (296)
1. December (20)
2. November (28)
3. October (15)
4. September (25)
5. August (30)
6. July (30)
7. June (22)
8. May (23)
9. April (32)
10. March (31)
11. February (18)
12. January (22)
3. 2022 (245)
4. 2021 (210)
5. 2020 (217)
6. 2019 (255)
7. 2018 (217)
8. 2017 (36)
9. 2016 (21)
10. 2015 (36)
11. 2014 (33)
12. 2013 (23)
13. 2012 (4)
14. 2011 (1)
15. 2010 (1)
16. 2009 (1)
17. 2008 (1)