NTU theorist resolving open problems in submodular maximization, online algorithms, and high-dimensional statistics
3
papers here
3
reviewed by Evolve
3
first-author
0
corresponding
—
works · OpenAlex
—
h-index · OpenAlex
Bibliometric figures come from OpenAlex (2026-10-16) and cover the author's entire public record, not just the papers listed here. Reproducibility signal comes from Evolve's own reviews.
Research profile
Output—
Not yet scored: total publication counts and venue history are not available in the current data, so research output cannot be measured. This axis would track the volume and cadence of published papers over time.
Impact—
Not yet scored: citation counts, h-index, and other influence metrics are absent from the current snapshot. This axis would measure how widely the work is cited and taken up by the research community.
Focus0/100
Scores 0 on this axis because the field distribution splits evenly across three distinct labels — submodular optimization and online algorithms, submodular optimization / online learning, and high-dimensional statistics / learning theory — each holding a 0.333 share in the raw fieldDist. The spread is partly a labeling artifact, since two labels describe the same submodular-optimization line, but the statistics line is a genuinely distinct second pillar.
Collaboration44/100
Scores 44, a moderate collaboration score, based on 8 distinct co-authors across the three reviewed papers. The frequentCoauthors list is dominated by Qixin Zhang, who appears in three of the eight co-authorship entries, followed by Dacheng Tao with two; Youming Qiao, Zongqi Wan, and Huibo Xu each appear once. All three cataloged papers are first-authored, suggesting a pattern of leading small theory collaborations rather than large consortia.
Activity—
Not yet scored: year-by-year publishing records beyond the three reviewed 2026 preprints are unavailable. This axis would measure recent research activity, such as annual publication rhythm and continuity of output.
Reproducibility70/100
Scores 70, the mean repro-readiness across three reviewed papers (reproPapers: 3). Paper-level readiness is rated high for the restricted-eigenvalues counterexample work and medium for both submodular maximization papers. Evolve verdicts note that the MGPE matroid paper assumes exact derivatives and reports no experiments, while the other two rest on rigorous, self-contained theory — a profile typical of proof-driven work whose artifacts are theorems and proofs rather than code.
Research summary
Shi Fu is a theoretical computer scientist at Nanyang Technological University whose reviewed work spans submodular optimization, online algorithms, and high-dimensional statistics. All three papers currently in the Evolve catalog are arXiv preprints dated 2026, and in each Shi Fu is the first author. Two papers attack open problems in submodular maximization: one resolves a STOC 2025 open problem by proving a sharp 2−√2≈0.586 barrier for consistent submodular maximization under polynomial queries and constant recourse, and the other lifts weak-submodular maximization over matroids from a (1+1/γ)⁻² guarantee toward ρ_γ→1−1/e via a Poisson-exchange (MGPE) algorithm. The third gives a negative answer to a COLT 2015 open problem on restricted eigenvalues under heavy-tailed designs, constructing pathwise constant-width counterexamples and proving a sharp VC occupancy law. The profile is method-driven: value-oracle lower bounds, query complexity, exchange properties, and small-ball techniques recur across the catalog. Radar dimensions computed from bibliometric data give reproducibility 70 (mean across three reviewed papers), collaboration 44 (eight distinct co-authors), and a focus score of 0 from an even three-way field split; output, impact, and activity metrics are not yet available.
Collaboration pattern
Collaboration is small-scale and theory-typical: 8 distinct co-authors across three first-authored papers. Qixin Zhang is the most frequent collaborator (3 of 8 co-authorship entries), followed by Dacheng Tao (2), with Youming Qiao, Zongqi Wan, and Huibo Xu appearing once each. The repeated pairing with Qixin Zhang suggests a stable core partnership, while the moderate score of 44 reflects a compact, lead-author-driven network rather than a broad one.
Research keywords
Highlights
Sharp 2−√2 barrier for consistent submodular maximization
Weak-submodular maximization over matroids lifted toward 1−1/e
Negative answer to a COLT 2015 restricted-eigenvalue open problem
Timeline
- 2026First-author arXiv preprint resolving the STOC 2025 open problem on consistent submodular maximization with a sharp 2−√2 barrier.
- 2026First-author arXiv preprint introducing Poisson-exchange algorithms for offline and online weak-submodular subset selection over matroids.
- 2026First-author arXiv preprint giving a negative answer to the COLT 2015 heavy-tailed restricted-eigenvalue open problem.
Papers in the Evolve catalog
- first author
Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
- first author
A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse
- first author
Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails
Frequent co-authors
About this profile
This profile is AI-structured by Evolve.Pub from public bibliographic data (OpenAlex) and Evolve's own paper reviews. It is not written or endorsed by the researcher unless the profile is claimed. Radar dimensions are computed from real bibliometrics with fixed formulas — raw figures are shown alongside; missing dimensions mean insufficient data, never zero. Errors? Claim the profile to correct or hide it.
- Bibliometric dimensions are computed from OpenAlex-derived data only; citation counts, h-index, and total publication volume were not available, so output, impact, and activity remain unscored.
- All three cataloged papers are 2026 arXiv preprints; peer-reviewed venue acceptance is not reflected in the current snapshot.
- "Shi Fu" is name-resolved from public bibliographic data; the profile covers only the reviewed catalog and should not be read as a complete publication record.
- No country, ORCID, or career-history data was provided; affiliation is limited to the stated institution (Nanyang Technological University).