The multiplicative complexity of interval checking
arXiv:2201.10200v15 citations
Originality Synthesis-oriented
AI Analysis
This addresses a fundamental problem in circuit complexity and optimization for researchers in theoretical computer science, though it appears incremental as it builds on known comparison methods.
The paper tackled the problem of determining the exact AND-gate cost for checking if a value lies within a constant integer interval, finding that this cost never exceeds that of a single comparison and can sometimes be lower.
We determine the exact AND-gate cost of checking if $a\leq x < b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never exceeds that of a single comparison and, in some cases, it is even lower.