Research map / Learning theory and algorithms / Submodular and game algorithms
Who Can Win a Single-Elimination Tournament?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Lower the CR Model upset-rate requirement to p ≥ C ln{n}/n, for C ≥ 64 | CR Model tournaments · CR Model tournaments | probability every player is an SE winner: p ≥ C ln{n}/n; ≥ 1-1/Ω(n^2) | Helped |
| Use a generalized model with random edges incident to each player in at least (1/2+Δ)n pairs | Generalized tournament model · Generalized tournament model | probability every player is an SE winner: p > c√(log{n}/(2Δn)); > 1-Ω(n^{(c-5)/2ln{2}}) | Helped |
| Combine the sufficient king conditions by partitioning the in-neighborhood into H, I, and J | King tournament-fixing conditions · Arbitrary tournaments | SE winner guarantee | Helped |
| Replace the prior perfect-matching requirement with the stated 3-king conditions | 3-king tournament-fixing conditions · Arbitrary tournaments | SE winner guarantee | Helped |
| Select a maximum k-path player for fixed k in a sufficiently large tournament | Iterative matrix tournament solution · Arbitrary tournaments | SE winner guarantee: there exists a constant N_k | Helped |
Closest papers by meaning
- Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable (AAAI 2017 · similarity 0.91)
- An Exercise in Tournament Design: When Some Matches Must Be Scheduled (AAAI 2024 · similarity 0.91)
- Adaptive Manipulation for Coalitions in Knockout Tournaments (AAAI 2025 · similarity 0.88)
- How to Make Knockout Tournaments More Popular? (AAAI 2024 · similarity 0.87)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.84)
- Competition among Pairwise Lottery Contests (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.