2 papers
cs.CC2026
A General Composition Theorem for Approximate Degree
Samruddhi Pednekar, Supartha Podder
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upp…
cs.CC2026
On the Approximate Non-Deterministic Degree of Total Boolean Functions
Samruddhi Pednekar, Supartha Podder
The approximate non-deterministic degree of a Boolean function , denoted (written for brevity), is the minimum degree of a real polynomial…