Pith. sign in

REVIEW 1 major objections 5 minor 141 references

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems

T0 review · 1 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read For every constraint satisfaction problem, a basic LP relaxation is as powerful, for approximation, as super-constant levels of the Sherali-Adams hierarchy.

desk verdict Real results, but the CSP lifting theorem has an unproven geometric coherence step; the polynomial and matrix norm chapters stand on much firmer ground. read the letter →

arxiv 2508.21327 v1 pith:DHKZB3Z7 submitted 2025-08-29 cs.CC cs.DS

Mrinalkanti Ghosh This is my paper
classification cs.CCcs.DS MSC 68Q1790C22
keywords Sherali-Adamshierarchyintegralitygapsconstraintsatisfactionproblemssum-of-squarespolynomialoptimizationmatrixnormshypercontractiveLPextendedformulations
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

This thesis studies what convex relaxation hierarchies can and cannot do for three optimization problems. The central CSP result is a dichotomy: for every predicate f and every (c,s) integrality-gap instance of the basic LP relaxation of MAX k-CSP(f), the same gap (up to epsilon) reappears at Omega(log N / log log N) levels of the Sherali-Adams hierarchy. Consequently, no polynomial-size LP extended formulation can beat the basic LP on such instances. For polynomial optimization over the sphere, the thesis gives a tradeoff between the level q of the sum-of-squares SDP and the approximation ratio, with better ratios for polynomials that are non-negative or sparse. For matrix p->q norms, it proves the first NP-hardness of approximation in the hypercontractive regime 1=q and 2 lies in [q,p].

What carries the argument

Three objects carry the arguments. (1) For CSPs: the (c,s)-integrality-gap instance of the basic LP used as a template, together with the locally l2-embeddable metric rho_mu on random hypergraphs and consistent partitioning schemes (built from separating decompositions of finite subsets of l2) that produce the local distributions satisfying Sherali-Adams consistency; the theorem that does the work is Theorem 2.1.1. (2) For polynomial optimization: the spectral relaxation value Lambda(h) = inf over matrix representations of the largest eigenvalue, which equals the SoS level-q optimum; the weak decoupling lemma relating Lambda(g)/||g||_inf to the multilinear components of g, and its folded-pol

What would settle it

For the CSP thread: exhibit a predicate f and a (c,s) basic-LP gap instance such that the Omega(log N/log log N)-level Sherali-Adams relaxation of the constructed random instance has value below c-epsilon; this would refute Theorem 2.1.1 directly. For the matrix thread: give a randomized polynomial-time algorithm approximating any hypercontractive ||A||_{p->q} (1<p<q<infinity, 2 not in [p,q]) within 2^{(log n)^{1-epsilon}} for some epsilon>0; this would contradict the claimed hardness (or show the derandomization assumption false).

Watch

Extended reading notes

Core claim

The load-bearing theorem of the CSP thread is Theorem 2.1.1: a (c,s) integrality gap for the basic LP of MAX k-CSP(f) implies, for every epsilon>0, (c-epsilon, s+epsilon) integrality gaps for c_epsilon * log N / log log N levels of the Sherali-Adams relaxation on instances of size N. Combined with the extended-formulation connection of [CLRS13, KMR17], this yields near-optimal lower bounds for every polynomial-size LP extended formulation of the problem. The theorem is proved by taking the basic-LP gap instance as a template and generating a random multipartite instance; the geometry of local l2-embeddable metrics on random hypergraphs is used to build consistent local distributions that foo

Load-bearing premise

The load-bearing premise is the quasi-polynomial derandomization assumption NP not subset BPTIME(2^{(log n)^{O(1)}}) for the matrix-norm NP-hardness, and, in the CSP thread, the local l2-embeddability guarantee for the metric rho on random hypergraphs; if either fails, the corresponding claimed lower bounds do not go through.

Editorial extensions

If this is right

  • For every predicate f, the entire approximability curve of the basic LP relaxation—not just its worst-case ratio—is inherited by the Omega(log N/log log N)-level Sherali-Adams relaxation, so improving the hierarchy beyond the basic LP is impossible in the worst case.
  • The dichotomy yields, via [KMR17], lower bounds of the form N^{c' log N/log log N} for any LP extended formulation that attempts to (c-epsilon, s+epsilon)-approximate a CSP with a basic-LP (c,s) gap; proving a basic-LP gap is thus sufficient to rule out all polynomial-size LPs.
  • For polynomial optimization over the sphere, level-q SoS, run in n^{O(q)} time, interpolates between the known n^{d/2-1} polynomial-time approximation (q=O(1)) and exactness for q=Omega(n); the paper's bounds are worst-case, instance-independent guarantees.
  • The tilde-Omega(n^{1/6}) gap for degree-4 non-negative polynomials shows that the SoS hierarchy, even at constant levels, cannot achieve a sub-polynomial worst-case approximation for a natural class of non-negative polynomials.
  • For p->q norms, any future algorithm beating 2^{(log n)^{1-epsilon}} in the hypercontractive case would either refute the derandomization assumption or settle a long-standing gap; in the regime p>=q with 2 in [q,p], the approximation ratio is pinned down up to numerical factors involving Grothendieck constants.

Reading between the lines

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

  • The CSP dichotomy suggests a practical proof strategy for LP lower bounds: construct only a basic-LP gap, which is often much easier than constructing a hierarchy-aware gap, and the hierarchy limitation follows automatically; this may be applicable to other hierarchy-based lower-bound programs beyond CSPs.
  • The weak decoupling lemma, which decouples without increasing variable count beyond 2n, might be useful in constrained polynomial optimization settings (e.g., the simplex or hypercube) and in sub-exponential algorithm design, as the thesis itself hints.
  • For matrix norms, the reliance on the quasi-polynomial derandomization assumption means the cleanest open target is to remove that assumption, or to show the reduction can be derandomized, which would upgrade the hardness to unconditional NP-hardness under P != NP.
  • The 'folding' technique suggests a testable prediction: for polynomials that decompose into low-degree easy parts, SoS at level q should converge roughly as (n/q)^{(d - d_easy)/2}, and one could verify this on structured instances such as 2->4 norms of tall matrices.
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

1 major / 5 minor

Summary. The thesis studies convex optimization hierarchies for three problems. Chapter 2 proves that a (c,s) integrality gap for the basic LP relaxation of any MAX k-CSP(f) can be lifted to a (c-ε,s+ε) integrality gap for Ω(log N / log log N) levels of the Sherali-Adams hierarchy, and via [KMR17] yields super-polynomial lower bounds for LP extended formulations. The proof constructs a random blown-up instance from the basic LP gap and uses local ℓ2-embeddable metrics to build consistent partitioning schemes. Chapter 3 studies approximating the maximum absolute value of a homogeneous polynomial over the unit sphere, proving level-q SoS tradeoffs for arbitrary, non-negative-coefficient, and sparse polynomials, as well as lower bounds for non-negative coefficients. Chapter 4 studies p→q matrix norms, giving hardness results for hypercontractive norms under a quasi-polynomial derandomization assumption and approximation algorithms for p ≥ q ≥ 2 cases. The thesis is generally detailed and mostly self-contained, though a few load-bearing steps are compressed.

Significance. If the results hold as stated, the CSP lifting theorem is a strong and elegant dichotomy: it says that a basic LP gap already captures the worst-case approximation behavior of super-constant-level Sherali-Adams relaxations for every predicate, with consequences for extended formulation lower bounds. The polynomial optimization results provide explicit level-vs-approximation tradeoffs and, notably, algorithms that do not solve the SDP; the non-negative-coefficient lower bound gives a polynomial integrality gap. The matrix norm results contribute the first hardness evidence for hypercontractive norms under a standard derandomization assumption and near-tight algorithms in the p ≥ q regime. The proofs are mostly constructive and detailed, and the use of geometry (ℓ2 embeddings, convex body diameter estimation, Banach space factorization) is coherent and well motivated.

major comments (1)
  1. [§2.5, Lemma 2.5.3 and Claim 2.5.5] The proof of Lemma 2.5.3 asserts, in one sentence, that for T ⊆ S the chosen ℓ2 embeddings W_S and W_T are nested up to a unitary transformation 'by the rigidity of ℓ2'. This is the only step that turns the per-set embeddings guaranteed by Theorem 2.3.5 into a coherent family of embeddings, and the consistency of the entire partitioning scheme (and hence of the Sherali-Adams solution in Lemma 2.6.4) depends on it. The assertion is not immediate from Theorem 2.3.5, which only says that each small set has some isometric embedding. The statement is nevertheless true for finite subsets of a Hilbert space: the isometry between the two copies of T extends to an orthogonal map of the ambient space, so adding a short proof (or a precise reference) is sufficient. As written, the manuscript leaves a load-bearing step unjustified and should be revised to include that argument.
minor comments (5)
  1. [§2.2.2, Fig. 2.1] The objective in the level-t Sherali-Adams LP is printed as f(α·b_C); it should presumably be f(α+b_C), consistent with the surrounding text and Fig. 2.2.
  2. [§2.5, Lemma 2.5.3 proof] The sentence 'for any S⊆T' appears to have the inclusion backwards; the subsequent use requires T⊆S. Please fix.
  3. [§3.2.1, Ineq. (3.6)] The overview says that the strengthening of Ineq. (3.5) to Ineq. (3.6) is shown in [BGG+17], but a proof appears later in §3.4.1 as Lemma 3.4.2. Please add a cross-reference to the in-manuscript proof to avoid the impression that a central step is deferred to an external full version.
  4. [§2.6.4, Lemma 2.6.4] The consistency step uses D_{𝒞(U_i)}|𝒞(V_i) = D_{𝒞(V_i)} by Lemma 2.6.3. This requires noting that 𝒞(V_i) is indeed a subtree of 𝒞(U_i) when V_i ⊆ U_i; the monotonicity of the closure operator makes this true, but it should be stated explicitly.
  5. [Throughout] There are several typographical and wording issues: 'for infinitely may N' in Theorem 2.6.7, 'we refer this difference as' in the introduction, and 'no random polynomial can approximate' in §3.6. A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the main claims are symbolic consequences of stated assumptions; the flagged gaps are correctness/completeness issues, not tautologies.

full rationale

I walked the three main derivation chains and found no step in which a claimed prediction or first-principles result is equivalent, by construction or by fitted parameter, to its own input. CSP thread (Theorem 2.1.1): The proof assumes a (c,s) basic-LP gap instance Phi0 and constructs a random instance whose SA_t solution is built directly from the assumed LP solution via tree propagation and a consistent partitioning scheme. Soundness uses OPT(Phi0)<s, completeness uses the LP solution as the starting point; the level-t solution is not the same object as the theorem's conclusion. The only real weakness is Lemma 2.5.3's assertion 'by the rigidity of ℓ2 we have that φ(W_T)⊆W_S', which is not proved and is not implied by the local embeddability theorem. That is a correctness/completeness gap, not a circular reduction: the conclusion does not follow by definition from the assumption, and the paper does not fit any parameter to force it. Polynomial optimization thread (Theorems 3.1.1, 3.4.15, 3.5.7, 3.5.8): The algorithms do not solve the SoS SDP; Λ(f^{q/d}) is used only as an analysis benchmark. The upper bounds on Λ(·) relative to ∥f∥∞ are obtained from inequalities such as Gershgorin, Perron-Frobenius, weak decoupling, and the folded-polynomial analogues. No constant is fitted to the target quantity; the approximation factors are derived symbolically from degree, sparsity, and q. The fact that the algorithm's guarantee is stated relative to the SoS optimum is an honest comparison, not a case of predicting a fitted value. Matrix-norm thread (Chapter 4): Hardness is proved under explicit derandomization assumptions (NP ⊄ BPTIME(2^{(log n)^{O(1)}})), and the approximation ratios use known constants from Gaussian projection/Hölder duals. No parameter is fitted from the claimed hardness value. Self-citations: The thesis defers some central inequalities to the companion full version [BGG+17], e.g. 'We show (see [BGG+17]) Λ(g) ≤ ...' (Section 3.2.1) and 'Implicit in our work (see [BGG+17]) is Theorem 3.2.2' (Section 3.2.2). These are completeness issues (omitted proofs) and self-references, but they are not load-bearing circular arguments: the cited inequalities are not asserted to be the same as the theorems being proved, and no uniqueness theorem from the same authors is used to forbid alternatives. Per the hard rules, self-citation alone is not circularity. Overall, no step reduces to its input by construction, so the circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 4 invented entities

The central claims rest on known theorems from metric geometry, SoS/SDP theory, and Banach space embeddings, plus one explicit quasi-polynomial complexity assumption. The proof-specific constructions are technical devices rather than fitted empirical parameters or postulated physical entities.

free parameters (3)
  • Constraint density gamma in gap construction = O((log q)/epsilon^2)
    Chosen in Lemmas 2.6.1 and 2.6.2 to make the soundness and basic-LP completeness arguments go through with the desired epsilon loss.
  • Partition scale mu and set-size t = mu = 2c log log n / log n, t about epsilon^2/(400 k^2 mu)
    Set in Lemma 2.6.4 to keep edge-cut probability below epsilon/2 while preserving t = Omega(log n/log log n).
  • Random graph density p for lower-bound polynomial = p = n^{-1/3}
    Chosen in Section 3.7 so that the 4-clique polynomial gives the stated n^{1/6} gap between ||f||_inf and Lambda(f).
assumptions (5)
  • standard math Local l2 embeddability theorem for l-path decomposable graphs (Theorem 2.4.10, from [CMM09])
    Used to prove Theorem 2.3.5 about local l2 embeddability of the metric rho_mu on random hypergraphs. The theorem is cited, not reproved in full.
  • standard math Separating decomposition theorem for finite subsets of l2 (Theorem 2.5.4, from [CCG+98])
    Used to construct consistent partitioning schemes in Section 2.5. The consistency modification is argued in Claim 2.5.5.
  • standard math Strong duality and SoS certificate characterization for sphere-constrained polynomial programs
    Invoked in Section 3.3 to justify that Lambda(f) equals the SoS SDP optimum and to prove Lemma 3.3.2. Based on standard SoS/SDP theory [Lau09, OZ13].
  • standard math Banach space embedding and factorization results, including approximate isometries and Grothendieck-type constants gamma_p*
    Used in Chapter 4 for both hardness reductions and the p-to-q rounding algorithm. The thesis relies on prior embedding theorems rather than proving them.
  • domain assumption Quasi-polynomial derandomization assumption NP not subset BPTIME(2^{(log n)^{O(1)}})
    Assumed in the hypercontractive matrix norm hardness result. This is not standard P != NP and is a load-bearing complexity assumption for the headline hardness claim.
invented entities (4)
  • Consistent partitioning schemes
    purpose: Build Sherali-Adams local distributions without paying exponential consistency cost
    Definition 2.5.1. A technical proof device, not an independently testable physical entity.
  • Folded polynomials
    purpose: Exploit easy substructures such as quadratics inside higher-degree polynomial optimization
    Introduced in Sections 3.2.2 and 3.5 to improve SoS approximation factors. A definitional device with no external empirical handle.
  • Holder-dual Gaussian rounding
    purpose: Round lp-bounded vectors arising from convex relaxations for p-to-q norms
    Introduced in Section 4.5.2 as a generalization of random hyperplane rounding. Validated only through the analysis in the thesis.
  • Tetris theorem decomposition
    purpose: Lift low-degree spectral lower bounds to higher levels of the spectral norm hierarchy
    Stated in Section 3.8.2 as a structural matrix decomposition. A mathematical tool, not an empirical entity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems." pith.science (2026). https://pith.science/paper/DHKZB3Z7

@misc{pith2026250821327,
  author       = {Pith},
  title        = {Pith review of: Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DHKZB3Z7}},
  note         = {Machine review of arXiv:2508.21327}
}
abstract

This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dichotomy of approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations: for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by super-constant levels of the Sherali-Adams hierarchy on instances of size $n$. - For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients. - We study the problem of approximating the $p \to q$-norm of a matrix $A$, and prove the first NP-hardness result for approximating norms in the hypercontractive case $1< p < q < \infty$. We also prove almost tight algorithmic results for the case when $p \geq q$ (with $2 \in [q,p]$) where constant factor approximations for the matrix norms are possible. A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.

Figures

Figures reproduced from arXiv: 2508.21327 by the authors.

Figure 2.1
Figure 2.1. Level-𝑡 Sherali-Adams LP for MAX k-CSP𝑞 (𝑓 ) on assignments that maximize expected satisfied constraint. Note that this, in itself, does not relax the problem as we can sample an assignment form the optimal distribution to get an opti￾mal assignment (the optimal distribution may be supported on one assignment). The relaxation happens by looking at the collection of “local distributions” with consistency constraints … view at source ↗
Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 2.2
Figure 2.2. Basic LP relaxation for MAX k-CSP𝑞 (𝑓 ) The main theorem we prove concerning the hardness of MAX k-CSP𝑞 in two different LP relax￾ations above: Theorem 2.1.1. Let 𝑓 : [𝑞] 𝑘 → {0, 1} be any predicate. Let Φ0 be a (𝑐, 𝑠) integrality gap instance for basic LP relaxation of MAX k-CSP (𝑓 ). Then for every 𝜀 > 0, there exists 𝑐𝜀 > 0 such that for infinitely many 𝑁 ∈ N, there exist (𝑐 − 𝜀, 𝑠 + 𝜀) integrality gap instances … view at source ↗
Figures from the paper (14 more)
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p035_2.png]
Figure 2.3
Figure 2.3. Figure 2.3: Construction of the gap instance Φ Soundness We first prove that no assignment satisfies more than 𝑠 + 𝜀 fraction of constraints for the above instance. Lemma 2.6.1. For every 𝜀 > 0, there exists 𝛾 = 𝛾(𝜀, 𝑛0, 𝑞) such that for an instance Φ generated by choosing at le…
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p044_2.png]
Figure 2.4
Figure 2.4. Figure 2.4: Sherali-Adams integrality gap instance for vanishing measure They show for a sufficiently large constant 𝛾, an instance Φ with 𝑚 = 𝛾 · 𝑛 constraints sat￾isfies with high probability, that for all assignments 𝜎, |satΦ(𝜎) − 𝜌(𝑓 )| ≤ 𝜀 (see Lemma 4.4 in [KTW14]). The pr…
Figure 2
Figure 2. Figure 2 [PITH_FULL_IMAGE:figures/full_fig_p045_2.png]
Figure 3
Figure 3. Figure 3 [PITH_FULL_IMAGE:figures/full_fig_p068_3.png]
Figure 3.1
Figure 3.1. Figure 3.1: Primal and dual forms for the relaxation computing Λ (𝑓 ) Primal ∥ 𝑓 ∥sp def = inf n ∥𝑀∥2 | 𝑀 ∈ S𝑛 𝑑/2 , (𝑥 ⊗𝑑/2 ) 𝑇 · 𝑀 · 𝑥 ⊗𝑑/2 = 𝑓 (𝑥) ∀𝑥 ∈ R 𝑛 o Dual maximize [PITH_FULL_IMAGE:figures/full_fig_p069_3_1.png]
Figure 3.2
Figure 3.2. Figure 3.2: Primal and dual forms for the relaxation computing ∥ 𝑓 ∥sp Properties of Relaxations Obtained from Constrained Pseudoexpectations We use the following claim, which is an easy consequence of the fact that the sum-of-squares algorithm can produce a certificate of optim…
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p119_4.png]
Figure 4.1
Figure 4.1. Figure 4.1: Upper and lower bounds for approximating ∥𝐴∥𝑝→𝑞. Arrows indicate the re￾gion to which a boundary belongs and thicker shaded regions represent exact algorithms. Our results are indicated by [∗]. We omit UGC-based hardness results in the figure. 111 [PITH_FULL_IMAGE:f…
Figure 4.2
Figure 4.2. Figure 4.2: A comparison of the bounds for approximating 𝑝 → 𝑝 ∗ obtained from Krivine’s rounding for 𝐾𝐺, Steinberg’s analysis, and our bound. While our analysis yields an improved bound for 4 ≤ 𝑝 ≤ 66, we believe that the rounding algorithm achieves an improved bound for all 𝑝.…
Figure 4.3
Figure 4.3. Figure 4.3: The relaxation CP(𝐴) for approximating 𝑝 → 𝑞 of a matrix 𝐴 ∈ R 𝑚×𝑛 . Next, we recall the relaxation due to Nesterov [Nes98]: Note that since 𝑞 ∗ ≥ 2 and 𝑝 ≥ 2, the above program is convex in the entries of the Gram matrix of the vectors  𝑢 𝑖 [PITH_FULL_IMAGE:figure…
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p173_4.png]
Figure 4.4
Figure 4.4. Figure 4.4: The Contour 𝑃(𝛼, 𝜀) Proof: For a contour 𝑃, we define 𝑉(𝑃) as 𝑉(𝑃) := 2 𝜋𝑘 ℑ ∫ 𝑃 𝑓 + 𝑎, 𝑏(𝑧) −𝑘 𝑑𝑧 As is evident from the integral representation, 𝑓 + 𝑎, 𝑏(𝑧) is purely imaginary if 𝑧 is purely imaginary, and as is evident from the power series, 𝑓𝑎, 𝑏(𝑧) is purely …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

141 extracted references · 74 canonical work pages

  1. [1]

    Towards strong nonapproximability results in the L ovasz- S chrijver hierarchy

    Michael Alekhnovich, Sanjeev Arora, and Iannis Tourlakis. Towards strong nonapproximability results in the L ovasz- S chrijver hierarchy. In Proceedings of the 37th ACM Symposium on Theory of Computing , pages 294--303, 2005

    2005

  2. [2]

    On non-approximability for quadratic programs

    Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, and Muli Safra. On non-approximability for quadratic programs. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on , pages 206--215. IEEE, 2005

    2005

  3. [3]

    A fast and simple randomized parallel algorithm for the maximal independent set problem

    Noga Alon, L \'a szl \'o Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms , 7(4):567--583, 1986

    1986

  4. [4]

    Proving integrality gaps without knowing the linear program

    Sanjeev Arora, B \'e la Bollob \'a s, and L \'a szl \'o Lov \'a sz. Proving integrality gaps without knowing the linear program. In Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science , pages 313--322. IEEE, 2002

    2002

  5. [5]

    Proving integrality gaps without knowing the linear program

    Sanjeev Arora, B \'e la Bollob \'a s, L \'a szl \'o Lov \'a sz, and Iannis Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing , 2(2):19--51, 2006

    2006

  6. [6]

    Adversarially robust low dimensional representations

    Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, and Aravindan Vijayaraghavan. Adversarially robust low dimensional representations. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory , volume 134 of Proceedings of Machine Learning Research , pages 237--325. PMLR, 15--19 Aug 2021

    2021

  7. [7]

    On the usefulness of predicates

    Per Austrin and Johan H stad. On the usefulness of predicates. ACM Trans. Comput. Theory , 5(1):1:1--1:24, May 2013

    2013

  8. [8]

    Topics in Banach space theory, volume 233 of Graduate Texts in Mathematics

    Fernando Albiac and Nigel J Kalton. Topics in Banach space theory, volume 233 of Graduate Texts in Mathematics . Springer, New York, 2006

    2006

Show all 141 references
  1. [9]

    Topics in Banach space theory , volume 233

    Fernando Albiac and Nigel John Kalton. Topics in Banach space theory , volume 233. Springer, 2006

    2006

  2. [10]

    Quadratic forms on graphs

    Noga Alon, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. Quadratic forms on graphs. Inventiones mathematicae , 163(3):499--522, 2006. Conference version in STOC '05

    2006

  3. [11]

    Approximating the cut-norm via G rothendieck's inequality

    Noga Alon and Assaf Naor. Approximating the cut-norm via G rothendieck's inequality. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing , STOC 2004, pages 72--80, New York, NY, USA, 2004. ACM

    2004

  4. [12]

    Woodruff

    Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, and David P. Woodruff. A PTAS for _p -Low Rank Approximation , pages 747--766. Society for Industrial and Applied Mathematics, 2019

    2019

  5. [13]

    Hypercontractivity, sum-of-squares proofs, and their applications

    Boaz Barak, Fernando GSL Brandao, Aram W Harrow, Jonathan Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages 307--326. ACM, 2012

    2012

  6. [14]

    Boaz Barak, Siu On Chan, and Pravesh K. Kothari. Sum of squares lower bounds from pairwise independence. In Proceedings of the 47th ACM Symposium on Theory of Computing , pages 97--106, New York, NY, USA, 2015. ACM

    2015

  7. [15]

    G rothendieck inequalities for semidefinite programs with rank constraint

    Jop Bri \"e t, Fernando M \'a rio de Oliveira Filho, and Frank Vallentin. G rothendieck inequalities for semidefinite programs with rank constraint. Theory Of Computing , 10(4):77--105, 2014

    2014

  8. [16]

    Weak decoupling, polynomial folds and approximate optimization over the sphere

    Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, and Madhur Tulsiani. Weak decoupling, polynomial folds and approximate optimization over the sphere. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, Octobe...

    2017

  9. [17]

    Deterministic and randomized polynomial-time approximation of radii

    Andreas Brieden, Peter Gritzmann, Ravindran Kannan, Victor Klee, L \'a szl \'o Lov \'a sz, and Mikl \'o s Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika , 48(1-2):63--105, 2001

    2001

  10. [18]

    Certifying random polynomials over the unit sphere via sum of squares hierarchy

    Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Certifying random polynomials over the unit sphere via sum of squares hierarchy. arXiv preprint arXiv:1605.00903 , 2016

    2016 arXiv

  11. [19]

    SDP gaps from pairwise independence

    Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pairwise independence. Theory of Computing , 8(12):269--289, 2012

    2012

  12. [20]

    Quantum de finetti theorems under local measurements with applications

    Fernando GSL Brandao and Aram W Harrow. Quantum de finetti theorems under local measurements with applications. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages 861--870. ACM, 2013

    2013

  13. [21]

    Estimating operator norms using covering nets

    Fernando GSL Brandao and Aram W Harrow. Estimating operator norms using covering nets. arXiv preprint arXiv:1509.05065 , 2015

    2015 arXiv

  14. [22]

    A nearly tight sum-of-squares lower bound for the planted clique problem

    Boaz Barak, Samuel B Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In Proceedings of the 57th annual IEEE symposium on Foundations of Computer Science , FOCS '16, pages 4...

    2016

  15. [23]

    Hypercontractivity and its applications

    Punyashloka Biswal. Hypercontractivity and its applications. arXiv preprint arXiv:1101.2913 , 2011

    2011 arXiv

  16. [24]

    Kelner, and David Steurer

    Boaz Barak, Jonathan A. Kelner, and David Steurer. Rounding sum-of-squares relaxations. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing , STOC 2014, pages 31--40, New York, NY, USA, 2014. ACM

    2014

  17. [25]

    Dictionary learning and tensor decomposition via the sum-of-squares method

    Boaz Barak, Jonathan A Kelner, and David Steurer. Dictionary learning and tensor decomposition via the sum-of-squares method. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing , pages 143--151. ACM, 2015

    2015

  18. [26]

    Kothari, and David Steurer

    Boaz Barak, Pravesh K. Kothari, and David Steurer. Quantum entanglement, sum of squares, and the log rank conjecture. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017, page 975–988, New York, NY, USA, 2017. Association for Computing Machinery

    2017

  19. [27]

    Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem

    Vijay Bhattiprolu, Euiwoong Lee, and Madhur Tulsiani. Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem . In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume 215 of Leibniz Intern...

    2022

  20. [28]

    Tensor prediction, rademacher complexity and random 3-xor

    Boaz Barak and Ankur Moitra. Tensor prediction, rademacher complexity and random 3-xor. arXiv preprint arXiv:1501.06521 , 2015

    2015 arXiv

  21. [29]

    The G rothendieck constant is strictly smaller than K rivine's bound

    Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. The G rothendieck constant is strictly smaller than K rivine's bound. In Forum of Mathematics, Pi , volume 1. Cambridge University Press, 2013. Conference version in FOCS '11

    2013

  22. [30]

    Briët , O

    J. Briët , O. Regev , and R. Saket . Tight hardness of the non-commutative G rothendieck problem. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , FOCS 2015, pages 1108--1122, Washington, DC, USA, 2015. IEEE Computer Society

    2015

  23. [31]

    Additive error guarantees for weighted low rank approximation

    Aditya Bhaskara, Aravinda Kanchana Ruwanpathirana, and Maheshakya Wijewardena. Additive error guarantees for weighted low rank approximation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning , volume 139 of Proceedin...

    2021

  24. [32]

    Expansion in Proof Complexity

    Eli Ben-Sasson. Expansion in Proof Complexity . PhD thesis, Hebrew University, 2001

    2001

  25. [33]

    Sum-of-squares proofs and the quest toward optimal algorithms

    Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms. arXiv preprint arXiv:1404.5236 , 2014

    2014 arXiv

  26. [34]

    Invertibility of large submatrices with applications to the geometry of banach spaces and harmonic analysis

    Jean Bourgain and Lior Tzafriri. Invertibility of large submatrices with applications to the geometry of banach spaces and harmonic analysis. Israel journal of mathematics , 57(2):137--224, 1987

    1987

  27. [35]

    Random tensors and planted cliques

    S Charles Brubaker and Santosh S Vempala. Random tensors and planted cliques. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages 406--419. Springer, 2009

    2009

  28. [36]

    Approximating matrix p-norms

    Aditya Bhaskara and Aravindan Vijayaraghavan. Approximating matrix p-norms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms , pages 497--511. SIAM, 2011

    2011

  29. [37]

    Approximating a finite metric by a small number of tree metrics

    Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science , pages 379--388, 1998

    1998

  30. [38]

    The missing log in large deviations for triangle counts

    Sourav Chatterjee. The missing log in large deviations for triangle counts. Random Structures & Algorithms , 40(4):437--451, 2012

    2012

  31. [39]

    Lee, Prasad Raghavendra, and David Steurer

    Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint satisfaction requires large LP relaxations. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science , pages 350--359, Washington, DC, USA, 2013. IEEE Computer Society

    2013

  32. [40]

    Local global tradeoffs in metric embeddings

    Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Local global tradeoffs in metric embeddings. In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science , pages 713--723, Washington, DC, USA, 2007. IEEE Computer Society

    2007

  33. [41]

    Near-optimal algorithms for maximum constraint satisfaction problems

    Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for maximum constraint satisfaction problems. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms , pages 62--68, 2007

    2007

  34. [42]

    Integrality gaps for S herali- A dams relaxations

    Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Integrality gaps for S herali- A dams relaxations. In Proceedings of the 41st ACM Symposium on Theory of Computing , pages 283--292, New York, NY, USA, 2009. ACM

    2009

  35. [43]

    Factoring weakly compact operators

    Wayne J Davis, Tadeusz Figiel, William B Johnson, and Aleksander Pe czy \'n ski. Factoring weakly compact operators. Journal of Functional Analysis , 17(3):311--327, 1974

    1974

  36. [44]

    Hopkins, Ankit Pensia, and Stefan Tiegel

    Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, and Stefan Tiegel. Sos certifiability of subgaussian distributions and its algorithmic applications. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1689–1700, New York, NY, USA, 2025....

    2025

  37. [45]

    The complexity of optimizing over a simplex, hypercube or sphere: a short survey

    Etienne De Klerk. The complexity of optimizing over a simplex, hypercube or sphere: a short survey. Central European Journal of Operations Research , 16(2):111--125, 2008

    2008

  38. [46]

    Upper tails for triangles

    Bobby DeMarco and Jeff Kahn. Upper tails for triangles. Random Structures & Algorithms , 40(4):452--459, 2012

    2012

  39. [47]

    Tight upper tail bounds for cliques

    Robert DeMarco and Jeff Kahn. Tight upper tail bounds for cliques. Random Structures & Algorithms , 41(4):469--487, 2012

    2012

  40. [48]

    A PTAS for the minimization of polynomials of fixed degree over the simplex

    Etienne de Klerk, Monique Laurent, and Pablo A Parrilo. A PTAS for the minimization of polynomials of fixed degree over the simplex. Theoretical Computer Science , 361(2):210--225, 2006

    2006

  41. [49]

    Convergence analysis for L asserre's measure--based hierarchy of upper bounds for polynomial optimization

    Etienne de Klerk, Monique Laurent, and Zhao Sun. Convergence analysis for L asserre's measure--based hierarchy of upper bounds for polynomial optimization. arXiv preprint arXiv:1411.6867 , 2014

    2014 arXiv

  42. [50]

    An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex

    Etienne de Klerk, Monique Laurent, and Zhao Sun. An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex. Mathematical Programming , 151(2):433--457, 2015

    2015

  43. [51]

    Decoupling: from dependence to independence

    Victor De la Pena and Evarist Gin \'e . Decoupling: from dependence to independence . Springer Science & Business Media, 2012

    2012

  44. [52]

    Linear programming relaxations of maxcut

    Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. Linear programming relaxations of maxcut. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms , pages 53--61, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics

    2007

  45. [53]

    Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems

    Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In COLT , pages 523--562, 2015

    2015

  46. [54]

    Convergence of sdp hierarchies for polynomial optimization on the hypersphere

    Andrew C Doherty and Stephanie Wehner. Convergence of sdp hierarchies for polynomial optimization on the hypersphere. arXiv preprint arXiv:1210.5048 , 2012

    2012 arXiv

  47. [55]

    Relations between average case complexity and approximation complexity

    Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing , STOC '02, page 534–543, New York, NY, USA, 2002. Association for Computing Machinery

    2002

  48. [56]

    A new approach to the planted clique problem

    Alan Frieze and Ravi Kannan. A new approach to the planted clique problem. In LIPIcs-Leibniz International Proceedings in Informatics , volume 2. Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2008

    2008

  49. [57]

    The dimension of almost spherical sections of convex bodies

    Tadeusz Figiel, Joram Lindenstrauss, and Vitali D Milman. The dimension of almost spherical sections of convex bodies. Acta Mathematica , 139(1):53--94, 1977

    1977

  50. [58]

    Block diagonally dominant matrices and generalizations of the gerschgorin circle theorem

    David G Feingold, Richard S Varga, et al. Block diagonally dominant matrices and generalizations of the gerschgorin circle theorem. Pacific J. Math , 12(4):1241--1250, 1962

    1962

  51. [59]

    Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms

    Rong Ge and Tengyu Ma. Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , page 829, 2015

    2015

  52. [60]

    Estimating the matrix p q norm, 2023

    Larry Guth, Dominique Maldague, and John Urschel. Estimating the matrix p q norm, 2023

    2023

  53. [61]

    R \'e sum \'e de la th \'e orie m \'e trique des produits tensoriels topologiques

    Alexandre Grothendieck. R \'e sum \'e de la th \'e orie m \'e trique des produits tensoriels topologiques . Soc. de Matem \'a tica de S \ a o Paulo, 1956

    1956

  54. [62]

    Bypassing UGC from some optimal geometric inapproximability results

    Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, and Yi Wu. Bypassing UGC from some optimal geometric inapproximability results. ACM Transactions on Algorithms (TALG) , 12(1):6, 2016. Conference version in SODA '12

    2016

  55. [63]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM , 42(6):1115–1145, November 1995

    1995

  56. [64]

    The best constants in the khintchine inequality

    Uffe Haagerup. The best constants in the khintchine inequality. Studia Mathematica , 70(3):231--283, 1981

    1981

  57. [65]

    Clique is hard to approximate within n 1-&epsiv

    Johan H stad. Clique is hard to approximate within n 1-&epsiv. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on , pages 627--636. IEEE, 1996

    1996

  58. [66]

    Clique is hard to approximate within n^ 1-

    Johan H stad. Clique is hard to approximate within n^ 1- . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science , FOCS 1996, pages 627--636, Washington, DC, USA, 1996. IEEE Computer Society

    1996

  59. [67]

    Some optimal inapproximability results

    Johan H stad. Some optimal inapproximability results. J. ACM , 48(4):798–859, July 2001

    2001

  60. [68]

    Improved NP-Inapproximability for 2-Variable Linear Equations

    Johan H stad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations . In Naveen Garg, Klaus Jansen, Anup Rao, and Jos \'e D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimizat...

    2015

  61. [69]

    The power of sum-of-squares for detecting hidden structures

    Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. Personal communication , 2017

    2017

  62. [70]

    Approximation algorithms for homogeneous polynomial optimization with quadratic constraints

    Simai He, Zhening Li, and Shuzhong Zhang. Approximation algorithms for homogeneous polynomial optimization with quadratic constraints. Mathematical Programming , 125(2):353--383, 2010

    2010

  63. [71]

    Testing product states, quantum M erlin- A rthur games and tensor optimization

    Aram W Harrow and Ashley Montanaro. Testing product states, quantum M erlin- A rthur games and tensor optimization. Journal of the ACM (JACM) , 60(1):3, 2013

    2013

  64. [72]

    Limitations of semidefinite programs for separable states and entangled games

    Aram W Harrow, Anand Natarajan, and Xiaodi Wu. Limitations of semidefinite programs for separable states and entangled games. arXiv preprint arXiv:1612.09306 , 2016

    2016 arXiv

  65. [73]

    Tensor principal component analysis via sum-of-square proofs

    Samuel B Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-square proofs. In Proceedings of The 28th Conference on Learning Theory , pages 956--1006, 2015

    2015

  66. [74]

    On the advantage over a random assignment

    Johan H stad and Srinivasan Venkatesh. On the advantage over a random assignment. Random Structures & Algorithms , 25(2):117--149, 2004

    2004

  67. [75]

    Stable distributions, pseudorandom generators, embeddings, and data stream computation

    Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM) , 53(3):307--323, 2006

    2006

  68. [76]

    On the complexity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences , 62(2):367--375, 2001

    2001

  69. [77]

    Upper tails for subgraph counts in random graphs

    Svante Janson, Krzysztof Oleszkiewicz, and Andrzej Ruci \'n ski. Upper tails for subgraph counts in random graphs. Israel Journal of Mathematics , 142(1):61--92, 2004

    2004

  70. [78]

    Hardness results for coloring 3-colorable 3-uniform hypergraphs

    Subhash Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on , pages 23--32. IEEE, 2002

    2002

  71. [79]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing , STOC '02, page 767–775, New York, NY, USA, 2002. Association for Computing Machinery

    2002

  72. [80]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the 34th ACM Symposium on Theory of Computing , pages 767--775, New York, NY, USA, 2002. ACM

    2002

  73. [81]

    S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for max-cut and other 2-variable csps? In 45th Annual IEEE Symposium on Foundations of Computer Science , pages 146--154, 2004

    2004

  74. [82]

    Measured descent: A new embedding method for finite metrics

    Robert Krauthgamer, James R Lee, Manor Mendel, and Assaf Naor. Measured descent: A new embedding method for finite metrics. Geometric & Functional Analysis GAFA , 15(4):839--858, 2005

    2005

  75. [83]

    Sum of squares lower bounds for refuting any CSP

    Pravesh Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP . In Proceedings of the 49th ACM Symposium on Theory of Computing , 2017. (To appear)

    2017

  76. [84]

    Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer

    Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017, pages 132--145, New York, NY, USA, 2017. ACM

    2017

  77. [85]

    Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSP s

    Pravesh Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSP s. In Proceedings of the 49th ACM Symposium on Theory of Computing , 2017. (To appear)

    2017

  78. [86]

    Woodruff

    Aditya Krishnan, Sidhanth Mohanty, and David P. Woodruff. On sketching q to p norms. Manuscript, 2018

    2018

  79. [87]

    Linear equations modulo 2 and the l\_1 diameter of convex bodies

    Subhash Khot and Assaf Naor. Linear equations modulo 2 and the l\_1 diameter of convex bodies. SIAM Journal on Computing , 38(4):1448--1463, 2008

    2008

  80. [88]

    Grothendieck-type inequalities in combinatorial optimization

    Subhash Khot and Assaf Naor. Grothendieck-type inequalities in combinatorial optimization. Communications on Pure and Applied Mathematics , 65(7):992--1035, 2012

    2012

  81. [89]

    The UGC hardness threshold of the L p G rothendieck problem

    Guy Kindler, Assaf Naor, and Gideon Schechtman. The UGC hardness threshold of the L p G rothendieck problem. Mathematics of Operations Research , 35(2):267--283, 2010. Conference version in SODA '08

    2010

  82. [90]

    SDP gaps and UGC -hardness for Max-Cut-Gain

    Subhash Khot and Ryan O'Donnell. SDP gaps and UGC -hardness for Max-Cut-Gain . Theory OF Computing , 5:83--117, 2009

    2009

  83. [91]

    On the approximability of digraph ordering

    Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, and Rishi Saket. On the approximability of digraph ordering. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings , pages 792--80...

    2015

  84. [92]

    Sur la constante de G rothendieck

    Jean-Louis Krivine. Sur la constante de G rothendieck. CR Acad. Sci. Paris Ser. AB , 284(8):A445--A446, 1977

    1977

  85. [93]

    Sdp integrality gaps with local _1 -embeddability

    Subhash Khot and Rishi Saket. Sdp integrality gaps with local _1 -embeddability. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science , pages 565--574, Washington, DC, USA, 2009. IEEE Computer Society

    2009

  86. [94]

    Approximating CSP s using LP relaxation

    Subhash Khot and Rishi Saket. Approximating CSP s using LP relaxation. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming , volume 9134, pages 822--833. Springer Verlag, 2015

    2015

  87. [95]

    The power of linear programming for general-valued CSP s

    Vladimir Kolmogorov, Johan Thapper, and Stanislav Z ivn\' y . The power of linear programming for general-valued CSP s. SIAM Journal on Computing , 44(1):1--36, 2015

    2015

  88. [96]

    A characterization of strong approximation resistance

    Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resistance. In Proceedings of the 46th ACM Symposium on Theory of Computing , pages 634--643, New York, NY, USA, 2014. ACM

    2014

  89. [97]

    Divide and conquer martingales and the number of triangles in a random graph

    Jeong Han Kim and Van H Vu. Divide and conquer martingales and the number of triangles in a random graph. Random Structures & Algorithms , 24(2):166--174, 2004

    2004

  90. [98]

    Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients

    Stanislaw Kwapie \'n . Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients. Stud. Math. , 44:583--595, 1972

    1972

  91. [99]

    On operators factorizable through l_p space

    Stanislaw Kwapie \'n . On operators factorizable through l_p space. M \'e moires de la Soci \'e t \'e Math \'e matique de France , 31:215--225, 1972

    1972

  92. [100]

    Moments, positive polynomials and their applications , volume 1

    Jean Bernard Lasserre. Moments, positive polynomials and their applications , volume 1. World Scientific, 2009

    2009

  93. [101]

    Sums of squares, moment matrices and optimization over polynomials

    Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry , pages 157--270. Springer, 2009

    2009

  94. [102]

    Hardness of graph pricing through generalized max-dicut

    Euiwoong Lee. Hardness of graph pricing through generalized max-dicut. In Proceedings of the 47th ACM Symposium on Theory of Computing , pages 391--399, New York, NY, USA, 2015. ACM

    2015

  95. [103]

    Daniel W. Lozier. NIST digital library of mathematical functions. Annals of Mathematics and Artificial Intelligence , 38(1):105--119, May 2003

    2003

  96. [104]

    Absolutely summing operators in L _p -spaces and their applications

    Joram Lindenstrauss and Aleksander Pe czy \'n ski. Absolutely summing operators in L _p -spaces and their applications. Studia Mathematica , 29(3):275--326, 1968

    1968

  97. [105]

    Lov \'a sz and A

    L. Lov \'a sz and A. Schrijver. Cones of matrices and set-functions and 0-1 optimization. SIAM J. on Optimization , 1(12):166--190, 1991

    1991

  98. [106]

    On the variational problem for upper tails in sparse random graphs

    Eyal Lubetzky and Yufei Zhao. On the variational problem for upper tails in sparse random graphs. Random Structures & Algorithms , 2016

    2016

  99. [107]

    Th \'e or \`e mes de factorisation pour les op \'e rateurs \`a valeurs dans un espace l_ p

    Bernard Maurey. Th \'e or \`e mes de factorisation pour les op \'e rateurs \`a valeurs dans un espace l_ p . S \'e minaire Analyse fonctionnelle (dit) , pages 1--5, 1974

    1974

  100. [108]

    A statistical model for tensor PCA

    Andrea Montanari and Emile Richard. A statistical model for tensor PCA . In Advances in Neural Information Processing Systems , pages 2897--2905, 2014

    2014

  101. [109]

    Semidefinite relaxation and nonconvex quadratic optimization

    Yurii Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization methods and software , 9(1-3):141--160, 1998

    1998

  102. [110]

    Random walk in a simplex and quadratic optimization over convex polytopes

    Yurii Nesterov. Random walk in a simplex and quadratic optimization over convex polytopes. Technical report, UCL, 2003

    2003

  103. [111]

    Krivine schemes are optimal

    Assaf Naor and Oded Regev. Krivine schemes are optimal. Proceedings of the American Mathematical Society , 142(12):4315--4320, 2014

    2014

  104. [112]

    Semidefinite programming relaxations of nonconvex quadratic optimization

    Yuri Nesterov, Henry Wolkowicz, and Yinyu Ye. Semidefinite programming relaxations of nonconvex quadratic optimization. In Handbook of semidefinite programming , pages 361--419. Springer, 2000

    2000

  105. [113]

    Approximating q p norms of non-negative matrices in nearly-linear time

    \'E tienne Objois and Adrian Vladu. Approximating q p norms of non-negative matrices in nearly-linear time. arXiv preprint arXiv:2503.19553 , 2025

    2025 arXiv

  106. [114]

    Approximability and proof complexity

    Ryan O'Donnell and Yuan Zhou. Approximability and proof complexity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1537--1556. Society for Industrial and Applied Mathematics, 2013

    2013

  107. [115]

    Absolut p-summierende abbildungen in normierten r \"a umen

    Albrecht Pietsch. Absolut p-summierende abbildungen in normierten r \"a umen. Studia Mathematica , 28(3):333--353, 1967

    1967

  108. [116]

    Un th e oreme sur les op e rateurs lin e aires entre espaces de banach qui se factorisent par un espace de hilbert

    Gilles Pisier. Un th e oreme sur les op e rateurs lin e aires entre espaces de banach qui se factorisent par un espace de hilbert. In Annales scientifiques de l E cole Normale Sup e rieure , volume 13, pages 23--43. Elsevier, 1980

    1980

  109. [117]

    Factorization of linear operators and geometry of Banach spaces

    Gilles Pisier. Factorization of linear operators and geometry of Banach spaces . Number 60. American Mathematical Soc., 1986

    1986

  110. [118]

    Grothendieck's theorem, past and present

    Gilles Pisier. Grothendieck's theorem, past and present. Bulletin of the American Mathematical Society , 49(2):237--323, 2012

    2012

  111. [119]

    Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP ? In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , STOC 2008, pages 245--254, New York, NY, USA, 2008. ACM

    2008

  112. [120]

    A new lower bound on the real G rothendieck constant

    JA Reeds. A new lower bound on the real G rothendieck constant. Manuscript, 1991

    1991

  113. [121]

    On subspaces of lp

    Haskell P Rosenthal. On subspaces of lp. Annals of Mathematics , pages 344--373, 1973

    1973

  114. [122]

    Strongly refuting random csps below the spectral threshold

    Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random csps below the spectral threshold. arXiv preprint arXiv:1605.00058 , 2016

    2016 arXiv

  115. [123]

    Integrality gaps for strong SDP relaxations of unique games

    Prasad Raghavendra and David Steurer. Integrality gaps for strong SDP relaxations of unique games. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science , 2009

    2009

  116. [124]

    Towards computing the G rothendieck constant

    Prasad Raghavendra and David Steurer. Towards computing the G rothendieck constant. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 525--534. Society for Industrial and Applied Mathematics, 2009

    2009

  117. [125]

    Graph expansion and the unique games conjecture

    Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the Forty-second ACM Symposium on Theory of Computing , STOC 2010, pages 755--764, New York, NY, USA, 2010. ACM

    2010

  118. [126]

    Sherali and Warren P

    Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. , 3(3):411--430, 1990

    1990

  119. [127]

    More on embedding subspaces of (l\_p ) in (l\^ n\_r )

    Gideon Schechtman. More on embedding subspaces of (l\_p ) in (l\^ n\_r ). Compositio Math , 61(2):159--169, 1987

    1987

  120. [128]

    Two observations regarding embedding subsets of euclidean spaces in normed spaces

    Gideon Schechtman. Two observations regarding embedding subsets of euclidean spaces in normed spaces. Advances in Mathematics , 200(1):125--135, 2006

    2006

  121. [129]

    Linear level L asserre lower bounds for certain k- CSP s

    Grant Schoenebeck. Linear level L asserre lower bounds for certain k- CSP s. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science , pages 593--602, Washington, DC, USA, 2008. IEEE Computer Society

    2008

  122. [130]

    Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

    Anthony Man-Cho So. Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems. Mathematical programming , 129(2):357--382, 2011

    2011

  123. [131]

    Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

    Anthony Man-Cho So. Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems. Math. Program. , 129(2):357–382, October 2011

    2011

  124. [132]

    On the Efficient Approximability of Constraint Satisfaction Problems

    Johan H stad. On the Efficient Approximability of Constraint Satisfaction Problems . In Surveys in Combinatorics , volume 346, pages 201--222. Cambridge University Press, 2007

    2007

  125. [133]

    On best lacunary systems of functions

    Sergei Borisovich Stechkin. On best lacunary systems of functions. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya , 25(3):357--366, 1961

    1961

  126. [134]

    Computation of matrix norms with applications to robust optimization

    Daureen Steinberg. Computation of matrix norms with applications to robust optimization. Research thesis, Technion-Israel University of Technology , 2005

    2005

  127. [135]

    Column subset selection, matrix factorization, and eigenvalue optimization

    Joel A Tropp. Column subset selection, matrix factorization, and eigenvalue optimization. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 978--986. Society for Industrial and Applied Mathematics, 2009

    2009

  128. [136]

    CSP gaps and reductions in the L asserre hierarchy

    Madhur Tulsiani. CSP gaps and reductions in the L asserre hierarchy. In Proceedings of the 41st ACM Symposium on Theory of Computing , pages 303--312, New York, NY, USA, 2009. ACM

    2009

  129. [137]

    The complexity of finite-valued CSP s

    Johan Thapper and Stanislav Z ivn\' y . The complexity of finite-valued CSP s. In Proceedings of the 45th ACM Symposium on Theory of Computing , pages 695--704, New York, NY, USA, 2013. ACM

    2013

  130. [138]

    The power of S herali- A dams relaxations for general-valued CSP s

    Johan Thapper and Stanislav Z ivn\' y . The power of S herali- A dams relaxations for general-valued CSP s. arXiv preprint arXiv:1606.02577 , 2016

    2016 arXiv

  131. [139]

    An application of F ourier methods to the problem of sharpening the B erry- E sseen inequality

    Paul van Beek. An application of F ourier methods to the problem of sharpening the B erry- E sseen inequality. Zeitschrift f \"u r Wahrscheinlichkeitstheorie und verwandte Gebiete , 23(3):187--196, 1972

    1972

  132. [140]

    High Dimensional Probability

    Roman Vershynin. High Dimensional Probability . 2017

    2017

  133. [141]

    A large deviation result on the number of small subgraphs of a random graph

    Van H Vu. A large deviation result on the number of small subgraphs of a random graph. Combinatorics, Probability & Computing , 10(1):79--94, 2001

    2001

Pith tools

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