Unconditional proof of tightness of Johnson bound

Venkatesan Guruswami*, Igor Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

2 Citations (Scopus)


A study was performed to prove a slightly weaker bound on Lpoly(δ) without making any number-theoretic assumption. It was shown that Lpoly(δ≤J(delta;)+γ0 for a very small absolute constant γ.

Original languageEnglish
Title of host publicationSODA '03 Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms
EditorsJ Schewel
Place of PublicationPhiladelphia, PA
PublisherSociety for Industrial and Applied Mathematics Publications
Number of pages2
ISBN (Print)0898715385
Publication statusPublished - 2003
Event14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003) - Baltimore, USA
Duration: 12 Jan 200314 Jan 2003


Conference14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)
CityBaltimore, USA


Dive into the research topics of 'Unconditional proof of tightness of Johnson bound'. Together they form a unique fingerprint.

Cite this