Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Faster Algorithms for Structured John Ellipsoid Computation
Authors: Yang Cao, Xiaoyu Li, Zhao Song, Xin Yang, Tianyi Zhou
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we focus on approximating the John Ellipsoid inscribed in a convex and centrally symmetric polytope defined by P := {x Rd : 1n Ax 1n}, where A Rn d is a rank-d matrix and 1n Rn is the all-ones vector. We develop two efficient algorithms for approximating the John Ellipsoid. The first is a sketchingbased algorithm that runs in nearly input-sparsity time e O(nnz(A) + dĪ), where nnz(A) denotes the number of nonzero entries in the matrix A and Ī 2.37 is the current matrix multiplication exponent. The second is a treewidth-based algorithm that runs in time e O(nĪ 2), where Ī is the treewidth of the dual graph of the matrix A. Our algorithms significantly improve upon the state-of-the-art running time of e O(nd2) achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019]. |
| Researcher Affiliation | Academia | Yang Cao Wyoming Seminary EMAIL Xiaoyu Li University of New South Wales EMAIL Zhao Song University of California, Berkeley EMAIL Xin Yang The University of Washington EMAIL Tianyi Zhou University of Southern California EMAIL |
| Pseudocode | Yes | Algorithm 1 Approximating John Ellipsoid inside symmetric polytopes, Algorithm 1 [CCLY19] Algorithm 2 Faster Algorithm for approximating John Ellipsoid inside symmetric polytopes Algorithm 3 Faster Algorithm for approximating John Ellipsoid (under tree width setting) |
| Open Source Code | No | Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments. |
| Open Datasets | No | The paper mentions "Netlib dataset" and "MATPOWER dataset" as examples to illustrate the relevance of treewidth. However, it does not use these datasets for any experiments within the paper itself, nor does it provide access information for data used in its own research. The paper's NeurIPS checklist explicitly states: "Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments." |
| Dataset Splits | No | The paper does not include experiments. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: The paper does not include experiments. |
| Hardware Specification | No | The paper does not include experiments. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The paper does not include experiments. |
| Software Dependencies | No | The paper does not include experiments. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments. |
| Experiment Setup | No | The paper does not include experiments. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: The paper does not include experiments. |