Settling the Matroid Secretary Problem

Zhiyi Huang

Settling the Matroid Secretary Problem

Zhiyi Huang

PreprintClaims a big step

In the authors' words

This paper settles the Matroid Secretary Problem with an $e$ -probability-competitive algorithm. The algorithm is ordinal and accesses arrived elements only through comparison and independence oracles, and has expected polynomial time and oracle complexity.

Main resultThe abstract does not state a limitation.

Read the paper PDF

Appeared: Monday, September 28. arXiv. Preprint, not yet peer-reviewed.

Computing Algorithms & complexity Sep 28, 2026
An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions
Our main result is an $O (n)$ space structure that encodes the nearest minimum cut between every pair of vertices.
Koustav Bhanja, Yotam Kenneth-Mordoch, Asaf Petruschka — arXiv
PreprintClaims a big step
Computing Algorithms & complexity Sep 28, 2026
KnottedGraph: Scalable knotted-graph topology for scientific and mathematical discovery
Here, we introduce KnottedGraph, a computational framework that converts such scientific representations to knotted graphs that retain graph connectivity and spatial embedding together.
Hakan Akg\"un, Xianquan Yan, Kehan Liu and 2 more — arXiv
PreprintBold claims, read criticallyCode available
Computing Algorithms & complexity Sep 28, 2026
Simulation-Efficient Analog Circuit Yield Optimization via Monte Carlo Zeroth-Order Gradient Estimation
We introduce zeroth-order Monte Carlo stochastic gradient descent (ZO-MC-SGD), a black-box method that converts continuous specification margins into stochastic descent directions.
Liyan Tan, Yequan Zhao, Ben F. Jamroz and 2 more — arXiv
PreprintReal-world use
Computing Algorithms & complexity Sep 28, 2026
From Segments to Trajectories: Evolving Affective Graphs with Evidence Retrieval for Continuous EEG Emotion Recognition
We propose EAGER, an Evolving Affective Graph framework with Evidence Retrieval for continuous EEG emotion recognition.
Chi Yang, Jihong Wang, Chengxi Xie and 5 more — arXiv
Preprint
Computing Algorithms & complexity Sep 28, 2026
A 120-State Binary Turing Machine Equivalent to the Riemann Hypothesis
We construct an explicit deterministic one-tape, two-symbol Turing machine with 120 working states whose blank-tape computation halts if and only if the Riemann hypothesis is false.
Joseph M. Shunia — arXiv
PreprintBold claims, read critically

All new papers on Algorithms & complexity

Settling the Matroid Secretary Problem

In the authors' words

More on Algorithms & complexity that day

An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions

KnottedGraph: Scalable knotted-graph topology for scientific and mathematical discovery

Simulation-Efficient Analog Circuit Yield Optimization via Monte Carlo Zeroth-Order Gradient Estimation

From Segments to Trajectories: Evolving Affective Graphs with Evidence Retrieval for Continuous EEG Emotion Recognition

A 120-State Binary Turing Machine Equivalent to the Riemann Hypothesis