Pith. sign in

REVIEW 6 minor 92 references

Hardness of A/E-Design under Partition Constraints

T0 review · 0 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Assuming P≠NP, A/E-design under partition constraints admits no efficient algorithm with approximation guarantee $2^{poly(d)+(1-\varepsilon)B}$.

desk verdict A correct, clean hardness result for A/E-design under partition constraints; the elementary 3-DM reduction verifies cleanly and deserves serious peer review. read the letter →

arxiv 2608.05468 v1 pith:ILQZ3DZ7 submitted 2026-08-05 cs.DS cs.DM

Nikhil Bansal , Yuze Xu This is my paper · ORCID
classification cs.DScs.DM MSC 68Q1768W2590C27
keywords A-optimaldesignE-optimalpartitionmatroidhardnessofapproximationthree-dimensionalmatchingexperimentalinapproximabilityPvsNP
topics P versus NP
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether A- and E-optimal design remain approximable when the chosen set of vectors must be a base of a partition matroid, and answers no: assuming P≠NP, any efficient algorithm must have approximation factor at least $2^{poly(d)+(1-\varepsilon)B}$, where $d$ is the dimension and $B$ is the maximum coordinate bit length. This is established by an elementary reduction from three-dimensional matching. The result matters because D-design, the sister objective, is known to admit poly$(d)$ estimation and approximation algorithms under the same matroid constraints, so A/E-design breaks the pattern. If correct, the problem has no reasonable approximation in general, resolving a question raised in earlier work on E-design with partition constraints.

What carries the argument

The load-bearing object is the block matrix $V_x=\begin{pmatrix} I_n & R\mathbf{1}_n & 0 \\ 0 & 1 & 0 \\ RA_x & R^2\mathbf{1}_m & I_m \end{pmatrix}$ and its exact inverse, Lemma 3.1. The construction chooses one vector per part, with triple parts offering either $u_i$ or $u_i+Ra_i$, and the special vector $w=h+R\sum_i u_i+R^2\sum_j e_j$ forces any base to represent $h$ with coefficients involving $Ax-\mathbf{1}_m$. The exact inverse places $R^2(Ax-\mathbf{1}_m)$ in a block, so the Frobenius norm formula for $A(x)$ follows immediately. It is this algebra that converts the combinatorial matching problem into a numeric gap between $R^4$ and $2dR^2$.

What would settle it

For the smallest instance, $m=3$, $n=1$, with $R=2$, write out the $5\times 5$ matrices $V_x$ from (7) and the proposed inverse from (8) for both $x=0$ and $x=1$, and multiply them by hand; if any block of the product deviates from the identity, especially the lower middle block where $R^2A_x\mathbf{1}_n$ must cancel, the claimed $R^4$ separation is wrong.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for every $\varepsilon\in(0,1)$, assuming P≠NP, no polynomial-time algorithm approximates A-design or E-design under partition constraints within factor $2^{poly(d)+(1-\varepsilon)B}$. The reduction builds $d=m+n+1$ dimensions and a partition matroid with $d$ singleton-or-pair parts; bases correspond exactly to 0/1 vectors $x$ indexed by triples. A perfect three-dimensional matching exists iff $Ax=\mathbf{1}_m$, and the gadget embeds the residual vector $R^2(Ax-\mathbf{1}_m)$ as a block of $V_x^{-1}$. Thus yes-instances have $A(x)\le 2dR^2$ while no-instances have $E(x)\ge R^4$, giving a separation ratio $R^2/(2d)$ that is tuned to be exponential in $B$.

Load-bearing premise

The whole gap rests on the exact block-inverse identity in Lemma 3.1; if that algebraic formula were wrong, the no-answer cost would not jump to $R^4$ while the yes-answer cost stays near $2dR^2$, and the claimed separation would collapse.

Editorial extensions

If this is right

  • No polynomial-time constant-factor or even subexponential-in-$B$ approximation exists for A/E-design under partition matroids, unless P=NP.
  • The known contrast with D-design is confirmed: D-design has poly$(d)$-guarantee algorithms for partition matroids, while A/E-design cannot.
  • The hardness transfers to rank $k>d$ by appending zero-vector parts, so allowing extra measurements does not make the problem tractable.
  • Because $E(x)\le A(x)\le dE(x)$, the same reduction certifies hardness for both objectives simultaneously.
  • The approximation must depend on the bit length $B$, so any tractable regime would have to constrain coordinate magnitudes or dimensions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The block-inverse gadget is reusable: any objective that reads a large block of $V_x^{-1}$ involving $\|Ax-\mathbf{1}_m\|$ will inherit the same hardness, so one can expect similar inapproximability for other spectral functions of $M(S)^{-1}$.
  • The result highlights precision, not just dimension, as an inherent source of intractability; algorithms for fixed dimension or strongly bounded coordinate size would not contradict the theorem.
  • A natural next target is to ask whether the same hardness holds for A/E-design under richer combinatorial constraints, such as intersections of two partition matroids or general matroids, since the current construction needs only simple partition constraints.
  • The exact inverse formula could be verified exhaustively on small random 3-DM instances by comparing it with brute-force computation of all bases, providing a concrete consistency test of the reduction's internal algebra.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies A- and E-optimal design under partition matroid constraints: given vectors v_1,...,v_N in R^d and a partition matroid, the goal is to choose a base S minimizing tr(M(S)^{-1}) (A-design) or lambda_max(M(S)^{-1}) (E-design), where M(S)=sum_{i in S} v_i v_i^top. The main result, Theorem 1.1, states that, assuming P != NP, for every epsilon in (0,1) there is no polynomial-time algorithm with approximation guarantee 2^{poly(d)+(1-epsilon)B}, where d is the dimension and B the maximum coordinate bit length. The proof gives an elementary reduction from three-dimensional matching. Each base corresponds to a 0/1 vector x of chosen triples, and the inverse of the associated matrix V_x contains the block R^2(Ax-1_m). A perfect matching exists iff some base has A-cost at most 2dR^2; otherwise every base has E-cost at least R^4. Choosing R = 2^{d^{c+1}} yields a gap of 2^{B-O(log d)}, which dominates the claimed approximation factor for suitably chosen c.

Significance. If the result holds, it answers an open question of Brown, Laddha and Singh [BLS24] and establishes a sharp contrast with D-design under matroid constraints, for which constant-factor estimation and polynomial approximation algorithms exist. The reduction is elementary and fully explicit: the exact inverse in Lemma 3.1 is verified by direct block multiplication, the completeness and soundness bounds in Lemma 3.2 are exact, and the gap calculation is parameter-free once R is chosen. The paper is short, readable, and the central argument is convincing. The remaining concerns are presentation-level: the quantifier over the polynomial p(d) in Theorem 1.1 and the treatment of small d are not fully spelled out, but both are straightforward to fix and do not affect the substance.

minor comments (6)
  1. [Section 3.2, proof of Theorem 1.1] The quantifier over c is imprecise: the proof fixes an integer c before specifying the polynomial p(d) in the approximation guarantee, yet later uses d^c to dominate 'any polynomial'. To make the proof rigorous, one should first fix an arbitrary polynomial p, then choose c (and R = 2^{d^{c+1}}) large enough so that p(d) <= d^c and epsilon B - O(log d) > d^c for all sufficiently large d.
  2. [Section 3.2, proof of Theorem 1.1] The statement 'For d large enough' needs an explicit treatment of small d. Since d = n+m+1, small d means bounded 3-DM instance size; such instances can be solved by brute force in constant time, or the instance can be padded to increase d. Please state this explicitly so the reduction covers all instances.
  3. [Section 3.1] The displayed definition 'R:= 2 dc+1' should read 'R := 2^{d^{c+1}}', and 'd c + (1-epsilon)B' should be 'd^c + (1-epsilon)B'; the exponents appear to have been lost in typesetting.
  4. [Section 3.2, Lemma 3.2] The phrase 'has squared Euclidean norm is at least R^4' should be 'has squared Euclidean norm at least R^4'.
  5. [Abstract] The sentence 'All coordinates with be integers' should read 'All coordinates will be integers'.
  6. [References] The citation '[L WZ25]' contains an unintended space and should be '[LWZ25]'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the hardness result rests on an explicit reduction from 3-DM, with no fitted parameters or load-bearing self-citation.

full rationale

The paper's central claim, Theorem 1.1, is an NP-hardness reduction from three-dimensional matching. The construction is fully explicit: each base S is put in bijection with a binary vector x, the induced matrix VS is written in block form (Equation 7), and the exact inverse is stated and verified by direct block multiplication in Lemma 3.1 (Equation 8). The completeness and soundness bounds in Lemma 3.2 are derived algebraically from that inverse, giving A(x) <= 2d R^2 when Ax=1_m and E(x) >= R^4 otherwise. The final bit-length and gap calculation is also explicit with R = 2^{d^{c+1}}. Nothing is fitted to data, no quantity being proved is imported through its own definition, and the only self-citation, [BS06], appears in a non-load-bearing related-work remark about the Santa Claus problem. The reduction is anchored to the external NP-completeness of 3-DM, so the derivation is self-contained and no circular step is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No parameters are fitted to data. The reduction uses a tunable integer R to amplify the gap; this is a standard hardness construction parameter, not a fitted model parameter, so it is not counted as a free parameter. The central claim rests on P≠NP and the NP-completeness of three-dimensional matching, both external benchmarks. There are no invented physical or mathematical entities.

assumptions (5)
  • domain assumption P ≠ NP
    The hardness theorem is conditional on this standard complexity assumption; if P=NP the conclusion would be vacuous.
  • standard math Three-dimensional matching is NP-complete
    Cited to Karp (1972); the reduction uses the decision version with incidence matrix A whose columns have exactly three ones.
  • standard math A perfect matching exists iff Ax = 1_m for some x in {0,1}^n
    This is the algebraic formulation of 3-DM used in Equation (3) of Section 2.
  • standard math E(S) ≤ A(S) ≤ d E(S) for invertible M(S)
    Stated in Section 2; used to transfer the upper bound on A to E and the lower bound on E to A in Lemma 3.2.
  • domain assumption Zero vectors are permitted as input vectors, so adding zero-vector parts extends hardness to rank k>d
    Stated in Section 2 after the rank assumption; if the problem required all v_i nonzero, this extension would need a different argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hardness of A/E-Design under Partition Constraints." pith.science (2026). https://pith.science/paper/ILQZ3DZ7

@misc{pith2026260805468,
  author       = {Pith},
  title        = {Pith review of: Hardness of A/E-Design under Partition Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ILQZ3DZ7}},
  note         = {Machine review of arXiv:2608.05468}
}
abstract

We consider the A/E-design problem under partition constraints: Given vectors $v_1,\ldots,v_N\in \R^d$ and a partition matroid on $[N]$, find a base $S$ of the matroid that minimizes $\tr(M(S)^{-1})$ or $\lambda_{\max}(M(S)^{-1})$ where $M(S)=\sum_{i \in S} v_i v_i^\top$. In contrast to D-design, where good estimation and approximation guarantees are known as a function of $d$, we show that no reasonable approximation exists for A/E-design. This answers a question of Brown, Laddha and Singh. The proof is based on an elementary reduction from three-dimensional matching.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

92 extracted references · 76 canonical work pages

  1. [1]

    SIAM Journal on Matrix Analysis and Applications , volume =

    Avron, Haim and Boutsidis, Christos , title =. SIAM Journal on Matrix Analysis and Applications , volume =

  2. [2]

    Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

    Anari, Nima and Oveis Gharan, Shayan , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

  3. [3]

    Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS) , year =

    Anari, Nima and Oveis Gharan, Shayan and Saberi, Amin and Singh, Mohit , title =. Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS) , year =

  4. [4]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Anari, Nima and Oveis Gharan, Shayan and Vinzant, Cynthia , title =. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    2018

  5. [5]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

    Anari, Nima and Liu, Kuikui and Oveis Gharan, Shayan and Vinzant, Cynthia , title =. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

  6. [6]

    , title =

    Anari, Nima and Mai, Tung and Oveis Gharan, Shayan and Vazirani, Vijay V. , title =. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

  7. [7]

    Flavors of Geometry , volume =

    Ball, Keith and others , title =. Flavors of Geometry , volume =

  8. [8]

    On the power of linear dependencies , booktitle =

    B. On the power of linear dependencies , booktitle =

Show all 92 references
  1. [9]

    Integer-making theorems , journal =

    Beck, J. Integer-making theorems , journal =

  2. [10]

    On some combinatorial questions in finite-dimensional spaces , journal =

    B. On some combinatorial questions in finite-dimensional spaces , journal =

  3. [11]

    Electronic Notes in Discrete Mathematics , volume =

    Bouhtou, Mustapha and Gaubert, Stephane and Sagnol, Guillaume , title =. Electronic Notes in Discrete Mathematics , volume =

  4. [12]

    Lorentzian polynomials , journal =

    Br. Lorentzian polynomials , journal =

  5. [13]

    Proceedings of the 2018 ACM Conference on Economics and Computation (EC) , pages =

    Barman, Siddharth and Krishnamurthy, Sanath Kumar and Vaish, Rohit , title =. Proceedings of the 2018 ACM Conference on Economics and Computation (EC) , pages =

    2018

  6. [14]

    Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS) , pages =

    Barman, Siddharth and Krishnamurthy, Sanath Kumar and Vaish, Rohit , title =. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS) , pages =

  7. [15]

    Boyd, Stephen and Vandenberghe, Lieven , title =

  8. [16]

    and Yazdanbod, Sadra , title =

    Cole, Richard and Devanur, Nikhil and Gkatzelis, Vasilis and Jain, Kamal and Mai, Tung and Vazirani, Vijay V. and Yazdanbod, Sadra , title =. Proceedings of the 2017 ACM Conference on Economics and Computation (EC) , pages =

    2017

  9. [17]

    Elisa and Deshpande, Amit and Kathuria, Tarun and Straszak, Damian and Vishnoi, Nisheeth K

    Celis, L. Elisa and Deshpande, Amit and Kathuria, Tarun and Straszak, Damian and Vishnoi, Nisheeth K. , title =. Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM) , series =

  10. [18]

    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , editor =

    Cevallos, Alfonso and Eisenbrand, Friedrich and Zenklusen, Rico , title =. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , editor =

  11. [19]

    Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pages =

    Carbonell, Jaime and Goldstein, Jade , title =. Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pages =

  12. [20]

    Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages =

    Cole, Richard and Gkatzelis, Vasilis , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages =

  13. [21]

    , title =

    Chen, Harr and Karger, David R. , title =. Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval , pages =

  14. [22]

    The unreasonable fairness of maximum nash welfare , booktitle =

    Caragiannis, Ioannis and Kurokawa, David and Moulin, Herv. The unreasonable fairness of maximum nash welfare , booktitle =

  15. [23]

    Elisa and Keswani, Vijay and Straszak, Damian and Deshpande, Amit and Kathuria, Tarun and Vishnoi, Nisheeth K

    Celis, L. Elisa and Keswani, Vijay and Straszak, Damian and Deshpande, Amit and Kathuria, Tarun and Vishnoi, Nisheeth K. , title =. Proceedings of the 35th International Conference on Machine Learning (ICML) , series =

  16. [24]

    Exponential inapproximability of selecting a maximum volume sub-matrix , journal =

  17. [25]

    and Tao, Terence , title =

    Candes, Emmanuel J. and Tao, Terence , title =. IEEE Transactions on Information Theory , volume =

  18. [26]

    Caron, Richard and Traynor, Tim , title =

  19. [27]

    The power of convex relaxation: near-optimal matrix completion , journal =

    Cand. The power of convex relaxation: near-optimal matrix completion , journal =

  20. [28]

    Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Di Summa, Marco and Eisenbrand, Friedrich and Faenza, Yuri and Moldenhauer, Carsten , title =. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

  21. [29]

    Symposium on Simplicity in Algorithms,

    Lap Chi Lau and Robert Wang and Hong Zhou , title =. Symposium on Simplicity in Algorithms,

  22. [30]

    and Straszak, Damian and Vishnoi, Nisheeth K

    Ebrahimi, Javad B. and Straszak, Damian and Vishnoi, Nisheeth K. , title =. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    2017

  23. [31]

    Portugaliae Mathematica , volume =

    Feichtner, Eva Maria and Sturmfels, Bernd , title =. Portugaliae Mathematica , volume =

  24. [32]

    Advances in Neural Information Processing Systems (NeurIPS) , pages =

    Gong, Boqing and Chao, Wei-Lun and Grauman, Kristen and Sha, Fei , title =. Advances in Neural Information Processing Systems (NeurIPS) , pages =

  25. [33]

    On maximin share allocations in matroids , journal =

    Gourv. On maximin share allocations in matroids , journal =

  26. [34]

    A matroid approach to the worst case allocation of indivisible goods , booktitle =

    Gourv. A matroid approach to the worst case allocation of indivisible goods , booktitle =

  27. [35]

    Near fairness in matroids , booktitle =

    Gourv. Near fairness in matroids , booktitle =

  28. [36]

    Grinberg, V. S. and Sevastjanov, S. V. , title =. Funktsionalny

  29. [37]

    Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC) , pages =

    Gurvits, Leonid , title =. Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC) , pages =

  30. [38]

    Advances in Combinatorial Mathematics , pages =

    Gurvits, Leonid , title =. Advances in Combinatorial Mathematics , pages =

  31. [39]

    Combinatorica , volume =

    Jain, Kamal , title =. Combinatorica , volume =

  32. [40]

    , title =

    Karmarkar, Narendra and Karp, Richard M. , title =. 23rd Annual Symposium on Foundations of Computer Science (SFCS) , pages =

  33. [41]

    Information Processing Letters , volume =

    Koutis, Ioannis , title =. Information Processing Letters , volume =

  34. [42]

    Foundations and Trends in Machine Learning , volume =

    Kulesza, Alex and Taskar, Ben and others , title =. Foundations and Trends in Machine Learning , volume =

  35. [43]

    IEEE Transactions on Information Theory , year =

    Li, Huan and Patterson, Stacy and Yi, Yuhao and Zhang, Zhongzhi , title =. IEEE Transactions on Information Theory , year =

  36. [44]

    Lau, Lap Chi and Ravi, Ramamoorthi and Singh, Mohit , title =

  37. [45]

    Fair Division and Collective Welfare , publisher =

    Moulin, Herv. Fair Division and Collective Welfare , publisher =

  38. [46]

    Conference on Learning Theory (COLT) , pages =

    Madan, Vivek and Singh, Mohit and Tantipongpipat, Uthaipon and Xie, Weijun , title =. Conference on Learning Theory (COLT) , pages =

  39. [47]

    Mohit Singh and Weijun Xie , title =. Math. Oper. Res. , volume =. 2020 , url =

    2020

  40. [48]

    Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC) , pages =

    Nikolov, Aleksandar , title =. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC) , pages =

  41. [49]

    Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages =

    Nikolov, Aleksandar and Singh, Mohit , title =. Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages =

  42. [50]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Nikolov, Aleksandar and Singh, Mohit and Tantipongpipat, Uthaipon Tao , title =. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

  43. [51]

    Pukelsheim, Friedrich , title =

  44. [52]

    Tyrrell , title =

    Rockafellar, R. Tyrrell , title =

  45. [53]

    Schrijver, Alexander , title =

  46. [54]

    Sevastjanov, S. V. , title =. Diskretny

  47. [55]

    Pacific Journal of Mathematics , volume =

    Sion, Maurice , title =. Pacific Journal of Mathematics , volume =

  48. [56]

    , title =

    Straszak, Damian and Vishnoi, Nisheeth K. , title =. 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages =

    2017

  49. [57]

    , title =

    Straszak, Damian and Vishnoi, Nisheeth K. , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages =

  50. [58]

    Symposium on Discrete Algorithms (SODA) , year =

    Singh, Mohit and Xie, Weijun , title =. Symposium on Discrete Algorithms (SODA) , year =

  51. [59]

    , title =

    Welch, William J. , title =. Journal of Statistical Computation and Simulation , volume =

  52. [60]

    Welsh, Dominic J. A. , title =

  53. [61]

    American Journal of Mathematics , volume =

    Whitney, Hassler , title =. American Journal of Mathematics , volume =

  54. [62]

    arXiv preprint arXiv:1601.02068 , year =

    Wang, Yining and Yu, Adams Wei and Singh, Aarti , title =. arXiv preprint arXiv:1601.02068 , year =

    arXiv

  55. [63]

    and Lafferty, John D

    Zhai, ChengXiang and Cohen, William W. and Lafferty, John D. , title =. SIGIR Forum , volume =

  56. [64]

    and Hovareshti, Pedram , title =

    Baras, John S. and Hovareshti, Pedram , title =. Proceedings of the 48th IEEE Conference on Decision and Control (CDC) held jointly with the 2009 28th Chinese Control Conference , pages =

    2009

  57. [65]

    Proceedings of the American Mathematical Society , volume =

    Brenti, Francesco , title =. Proceedings of the American Mathematical Society , volume =

  58. [66]

    Comtet, Louis , title =

  59. [67]

    IEEE Transactions on Signal Processing , volume =

    Joshi, Siddharth and Boyd, Stephen , title =. IEEE Transactions on Signal Processing , volume =

  60. [68]

    Journal of Complexity , volume =

    Khachiyan, Leonid , title =. Journal of Complexity , volume =

  61. [69]

    , title =

    Khachiyan, Leonid G. , title =. Mathematics of Operations Research , volume =

  62. [70]

    Information Processing Letters , volume =

    Lee, Euiwoong , title =. Information Processing Letters , volume =

  63. [71]

    Foundations of Computer Science (FOCS) , pages =

    Madan, Vivek and Nikolov, Aleksandar and Singh, Mohit and Tantipongpipat, Uthaipon , title =. Foundations of Computer Science (FOCS) , pages =

  64. [72]

    Proceedings of the Conference on Learning Theory (COLT) , pages =

    Thiery, Theophile and Ward, Justin , title =. Proceedings of the Conference on Learning Theory (COLT) , pages =

  65. [73]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Garg, Jugal and Hoefer, Martin and Mehlhorn, Kurt , title =. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

  66. [74]

    Approximating nash social welfare under rado valuations , booktitle =

    Garg, Jugal and Husi. Approximating nash social welfare under rado valuations , booktitle =

  67. [75]

    A constant-factor approximation algorithm for nash social welfare with submodular valuations , booktitle =

    Li, Wenzheng and Vondr. A constant-factor approximation algorithm for nash social welfare with submodular valuations , booktitle =

  68. [76]

    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Lau, Lap Chi and Zhou, Hong , title =. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    2021

  69. [77]

    Marcus and Daniel A

    Adam W. Marcus and Daniel A. Spielman and Nikhil Srivastava , title =. Ann. of Math. (2) , volume =

  70. [78]

    Marcus and Daniel A

    Adam W. Marcus and Daniel A. Spielman and Nikhil Srivastava , title =. Israel J. Math. , volume =

  71. [79]

    Symposium on Theory of Computing (STOC) , pages =

    Nima Anari and Shayan Oveis Gharan , title =. Symposium on Theory of Computing (STOC) , pages =

  72. [80]

    Symposium on Foundations of Computer Science (FOCS) , pages =

    Nima Anari and Shayan Oveis Gharan and Cynthia Vinzant , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

  73. [81]

    Mathematical Programming , volume =

    Zeyuan Allen-Zhu and Yuanzhi Li and Aarti Singh and Yining Wang , title =. Mathematical Programming , volume =

  74. [82]

    arXiv preprint arXiv:2211.10507 , year =

    Adam Brown and Aditi Laddha and Madhusudhan Pittu and Mohit Singh , title =. arXiv preprint arXiv:2211.10507 , year =

    arXiv

  75. [83]

    Symposium on Foundations of Computer Science (FOCS) , pages =

    Adam Brown and Aditi Laddha and Madhusudhan Pittu and Mohit Singh and Prasad Tetali , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

  76. [84]

    Foundations of Computer Science,

    Deeparnab Chakrabarty and Julia Chuzhoy and Sanjeev Khanna , title =. Foundations of Computer Science,. 2009 , url =

    2009

  77. [85]

    The Santa Claus problem , booktitle =

    Nikhil Bansal and Maxim Sviridenko , editor =. The Santa Claus problem , booktitle =

  78. [86]

    Operations Research Letters , volume =

    Adam Brown and Aditi Laddha and Mohit Singh , title =. Operations Research Letters , volume =

  79. [87]

    Karp , title =

    Richard M. Karp , title =. Complexity of Computer Computations , pages =

  80. [88]

    SIAM Journal on Computing , volume =

    Lap Chi Lau and Hong Zhou , title =. SIAM Journal on Computing , volume =

  81. [89]

    Foundations of Computer Science (FOCS) , pages =

    Vivek Madan and Aleksandar Nikolov and Mohit Singh and Uthaipon Tantipongpipat , title =. Foundations of Computer Science (FOCS) , pages =

  82. [90]

    Symposium on Theory of Computing (STOC) , pages =

    Aleksandar Nikolov and Mohit Singh , title =. Symposium on Theory of Computing (STOC) , pages =

  83. [91]

    Mathematics of Operations Research , volume =

    Aleksandar Nikolov and Mohit Singh and Uthaipon Tantipongpipat , title =. Mathematics of Operations Research , volume =

  84. [92]

    Friedrich Pukelsheim , title =

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.