Proves the stronger rational-degree conjecture holds with polynomial bounds for monotone, unate, bounded-alternation, symmetric, k-uniform hypergraph, and read-k DNF total Boolean functions.
Computing with a full memory: catalytic space , booktitle = STOC, pages =
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
years
2026 3verdicts
UNVERDICTED 3representative citing papers
Deterministic (1+ε)-approximation algorithm for the volume of the unit hypercube truncated by k sums-of-univariate-convex constraints, running in poly_k(n, 1/ε, L, L_o) time.
Three new robust error models for catalytic tape resetting are characterized with equivalences to standard classes and collapse under derandomization.
citing papers explorer
-
On the Approximate Non-Deterministic Degree of Total Boolean Functions
Proves the stronger rational-degree conjecture holds with polynomial bounds for monotone, unate, bounded-alternation, symmetric, k-uniform hypergraph, and read-k DNF total Boolean functions.
-
Deterministic Volume Estimation of Truncated Hypercubes
Deterministic (1+ε)-approximation algorithm for the volume of the unit hypercube truncated by k sums-of-univariate-convex constraints, running in poly_k(n, 1/ε, L, L_o) time.
-
Understanding Robust Catalytic Computing
Three new robust error models for catalytic tape resetting are characterized with equivalences to standard classes and collapse under derandomization.