Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
The adaptive complexity of maximizing a submodular function , booktitle =
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
years
2026 3verdicts
UNVERDICTED 3representative citing papers
An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ learning of halfspaces via iterative Forster transforms.
Averaged constraints on conditional effects in causal masking almost surely yield policies that violate stratum-wise independence while satisfying the averaged constraint, with larger gains under confounding and heterogeneity.
citing papers explorer
-
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
-
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ learning of halfspaces via iterative Forster transforms.
-
Masking Causality and Conditional Dependence
Averaged constraints on conditional effects in causal masking almost surely yield policies that violate stratum-wise independence while satisfying the averaged constraint, with larger gains under confounding and heterogeneity.