The complexity of semidefinite programs for testing $k$-block-positivity

• URL: http://arxiv.org/abs/2601.19159v1
• Date: Tue, 27 Jan 2026 03:46:06 GMT
• Title: The complexity of semidefinite programs for testing $k$-block-positivity
• Abstract summary: We extend citechen2025srkbp by analyzing the complexity of the $k$-block-positivity testing algorithm.
• Score: 4.02230249930341
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We extend \cite{chen2025srkbp} by analyzing the complexity of the $k$-block-positivity testing algorithm. In this paper, we investigate a symmetry reduction scheme based on rectangular shaped Young diagrams. Connecting the complexity to the dimensions of irreducible representations of $\mathrm{U}(d)$, we derive an explicit formula for the complexity, which also clarifies why the semidefinite program hierarchy collapses in the $k=d$ case.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Replicable Composition [35.262362690798014]
  We show that problems with sample complexities can be jointly solved with $widetildeO(sum_i n_i)$ samples while preserving replicability.<n>Our approach converts each replicable algorithm into a perfectly generalizing one, composes them via a privacy-style analysis, and maps back via correlated sampling.
  arXiv  Detail & Related papers  (2026-04-12T02:43:42Z)
• CSPs with Few Alien Constraints [12.330326247154968]
  We consider CSP$(mathcalA cup mathcalB)$ where $mathcalA$ is a structure and $mathcalB$ is an alien structure. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts.
  arXiv  Detail & Related papers  (2024-08-23T08:34:13Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Randomised Composition and Small-Bias Minimax [0.9252523881586053]
  We prove two results about query complexity $mathrmR(f)$. First, we introduce a "linearised" complexity measure $mathrmLR$ and show that it satisfies an inner-conflict composition theorem: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$ and $g$, and moreover, $mathrmLR$ is the largest possible measure with this property.
  arXiv  Detail & Related papers  (2022-08-26T23:32:19Z)
• On the Sample Complexity of Privately Learning Axis-Aligned Rectangles [16.092248433189816]
  We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid. We present a novel algorithm that reduces the sample complexity to only $tildeOleftdcdotleft(log*|X|right)1.5right$.
  arXiv  Detail & Related papers  (2021-07-24T04:06:11Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent PAC model. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem.
  arXiv  Detail & Related papers  (2020-07-30T04:18:51Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  We show that the average-case teaching complexity is $Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $Theta(n)$. Our insights allow us to establish a tight bound on the average-case complexity for $phi$-separable dichotomies.
  arXiv  Detail & Related papers  (2020-06-25T19:59:24Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• Complexity of Shapes Embedded in ${\mathbb Z^n}$ with a Bias Towards Squares [0.0]
  Shape complexity is a hard-to-quantify quality, mainly due to its relative nature. We consider squares to be the simplest shapes relative to which complexity orders are constructed.
  arXiv  Detail & Related papers  (2020-03-16T17:24:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.