Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle.
Aaron PotechinAaron ZhangPublished in: ICALP (2024)
Keyphrases
- lower bound
- upper bound
- worst case
- window size
- theorem proving
- formal proof
- scales linearly
- information retrieval
- multiscale
- computational complexity
- database
- sufficient conditions
- worst case bounds
- tight bounds
- lower and upper bounds
- space complexity
- inference rules
- error bounds
- search engine
- machine learning
- neural network
- real time