Talks
Spring 2017

Approximately Counting Solutions to Systems of Quadratic Equations
Monday, March 6th, 2017, 10:00 am–10:30 am
Speaker:
Location:
Calvin Lab Auditorium
We give a deterministic poly(n)/epsilon^2 time algorithm for approximately counting (to within epsilon) the fraction of solutions to a system of quadratic n-variate equations over F2. Note that random sampling would yield a similar running time in terms of n and epsilon.