3 papers
cs.CC2025
Catalytic Computing and Register Programs Beyond Log-Depth
Yaroslav Alekseev, Yuval Filmus, Ian Mertz +2
In a seminal work, Buhrman et al. (STOC 2014) defined the class of problems solvable in space with an additional catalytic tape of size , which is a tape whose…
cs.DS2025
Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
Yuval Filmus, Roy Schwartz, Alexander V. Smal
We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy…
cs.LO2025
Simplifier: A New Tool for Boolean Circuit Simplification
Daniil Averkov, Gregory Emdin, Viktoriia Krivogornitsyna +4
The Boolean circuit simplification problem involves finding a smaller circuit that computes the same function as a given Boolean circuit. This problem is closely related to several…