15 citations · 21 across the 14 of their papers we have counts for
Showing 2026 · cs.CCShow all
3 papers · 2 filters
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
Promises should be taken seriously: On relativization with promise problems
David Miloschewsky, Supartha Podder, Dorian Rudolph
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of…
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…