Certifying the quasirandomness of hypergraphs

Luca Trevisan
University of California, Berkeley (UC Berkeley)

There are two approaches to efficiently verifying the quasirandomness of a given graph: by counting the number of 4-cycles (which works only on dense graphs) and via spectral considerations (which works for sparse graphs as well). Arguments based on counting local patterns give efficient algorithms to verify the quasirandomness of a given dense hypergraph as well, but no efficient algorithms are known for sparse hypergraphs. We review known results on the related problem of certifying the unsatisfiability of a given random kSAT formula, and the implications of such results for the problem of certifying quasirandomness of sparse hypergraphs.


Back to Expanders in Pure and Applied Mathematics