Computer Science/Discrete Mathematics

Date:
Mar
08
2021

Computer Science/Discrete Mathematics Seminar I

Strong refutation of semi-random Boolean CSPs
Venkatesan Guruswami
11:15am|Remote Access - see Zoom link below

For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n...

Mar
09
2021

Computer Science/Discrete Mathematics Seminar II

Random k-out subgraphs
Or Zamir
10:30am|Simonyi Hall 101 and Remote Access - see Zoom link below

Random sampling a subgraph of a graph is an important algorithmic technique.  Solving some problems on the (smaller) subgraph is naturally faster, and can give either a useful approximate answer, or sometimes even give a result that can be quickly...

Mar
10
2021

Stability and Testability

Constraint metric approximation and constraint stability
Liviu Paunescu
11:00am|Remote Access
Constraint metric approximation is about constructing an approximation of a group $G$, when the approximation is already given for a subgroup $H$. Similarly, constraint stability is about lifting a representation of a group $G$, when the lift is...
Mar
17
2021

Stability and Testability

Approximate representations of symplectomorphisms via quantization
Leonid Polterovich
11:00am|Remote Access
We argue that quantization, a mathematical model of the quantum classical correspondence, gives rise to approximate unitary representations of symplectomorphism groups. As an application, we get an obstruction to symplectic action of Lubotzky...