Tags » Polynomial Method

Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization

In the post Balls in Bins I wrote about a combinatorial function which denotes the minimum value of the product among all distributions of balls (so ) in bins with the constraints . 728 more words


A timeline of the polynomial method up-to combinatorial nullstellensatz

Over the past 30-40 years, the so-called polynomial method has developed into a powerful tool in combinatorics and (additive) number theory. There has been a lot of recent interest in it after Dvir’s  … 627 more words

Finite Geometry

On Zeros of a Polynomial in a Finite Grid: the Alon-Furedi bound

My joint paper with Aditya Potukuchi, Pete L. Clark and John R. Schmitt is now up on arXiv: arXiv:1508.06020.

This work started a few months back when I emailed Pete and John, pointing out an easy generalization of Chevalley-Warning theorem using something known as the… 244 more words

Finite Geometry

Chevalley-Warning Theorem and Blocking Sets

The classical Chevalley-Warning theorem gives us a sufficient condition for a system of polynomial equations over a finite field to have common solutions. Affine blocking sets… 635 more words

Polynomial Method

Balls in Bins

When I was learning combinatorics for the first time (I was probably 16) there was this problem about distributing balls in bins (or urns) that I came across. 535 more words


The Kakeya problem

The original Kakeya needle problem  is to  find the least amount of area required to continuously rotate a unit line segment in the (Euclidean) plane by a full rotation… 978 more words

Finite Geometry

Two proofs of the Schwartz-Zippel lemma

The fact that a univariate polynomial over a field of degree has at most zeroes is well known. It follows from the so called Factor theorem, if and only if . 907 more words

Finite Geometry