Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
On the Rational Degree of Boolean Functions and Applications
Vishnu Iyer, Siddhartha Jain, Robin Kothari +5
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted , it is the minimal degree of a rational function that is equal t…
cs.CC2025
New Pseudorandom Generators and Correlation Bounds Using Extractors
Vinayak M. Kumar
We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalizations of structured low-degree -…