Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2008 | public
Journal Article

Bounds on degrees of p-adic separating polynomials

Abstract

We study a discrete optimization problem introduced by Babai, Frankl, Kutin, and Stefankovic (2001), which provides bounds on degrees of polynomials with p-adically controlled behavior. Such polynomials are of particular interest because they furnish bounds on the size of set systems satisfying Frankl-Wilson-type conditions modulo prime powers, with lower degree polynomials providing better bounds. We elucidate the asymptotic structure of solutions to the optimization problem, and we also provide an improved method for finding solutions in certain circumstances.

Additional Information

© 2008 Elsevier Inc. Received 18 July 2007. Available online 17 March 2008. Communicated by Bruce Rothschild. The authors wish to thank Richard M. Wilson for his helpful advice on this work and its presentation.

Additional details

Created:
August 22, 2023
Modified:
October 18, 2023