Spring 2017

Approximately Counting Solutions to Systems of Quadratic Equations

Monday, March 6th, 2017 10:00 am10:30 am

Add to Calendar


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.