Computer Science/Discrete Mathematics

Date:
Nov
23
2020

Computer Science/Discrete Mathematics Seminar I

New isoperimetric inequalities for convex bodies
11:15am|Remote Access Only - see link below

What can we say on a convex body from seeing its projections? In the 80s, Lutwak introduced a collection of measurements that capture this question. He called them the affine quermassintegrals. They are affine invariant analogues of the classical...

Nov
24
2020

Computer Science/Discrete Mathematics Seminar II

Factorization through L2, Rounding and Duality Part 2
10:30am|Remote Access Only - see link below

Let X and Y be normed spaces. In functional analysis, a ``theorem on factorization through L2'' refers to the following type of statement: 

Every bounded linear operator A mapping X to Y (i.e. sup_x ||A(x)||_Y/||x||_X

Such factorization...

Nov
25
2020

Stability and Testability

Approximations of groups, subquotients of infinite direct products and equations over groups
Lev Glebsky
11:00am|Remote Access - see Zoom link below

Let C be a class of groups. (For example, C is a class of all finite groups, or C is a class of all finite symmetric groups.) I give a definition of approximations of a group G by groups from C. For example, the groups approximable by symmetric...

Nov
30
2020

Computer Science/Discrete Mathematics Seminar I

Thresholds for Random Subspaces, aka, LDPC Codes Achieve List-Decoding Capacity
Mary Wootters
11:15am|Remote Access - see Zoom link below

What combinatorial properties are likely to be satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball of fixed radius? What about any combinatorial rectangle of fixed side...

Dec
02
2020

Stability and Testability

Stability, cohomology vanishing, and non-approximable groups
Andreas Thom
11:00am|Remote Access - see Zoom link below

Several well-known open questions (such as: are all groups sofic/hyperlinear?) have a common form: can all groups be approximated by asymptotic homomorphisms into the symmetric groups $Sym(n)$ (in the sofic case) or the finite dimensional unitary...

Dec
07
2020

Computer Science/Discrete Mathematics Seminar I

Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning
Sumegha Garg
11:15am|Remote Access - see Zoom link below

A recent line of work has focused on the following question: Can one prove strong unconditional lower bounds on the number of samples needed for learning under memory constraints? We study an extractor-based approach to proving such bounds for a...