Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Randomization and Approximation Techniques in Computer Science

On the Hardness of Approximate Multivariate Integration.

Ioannis Koutis

Published Jan 1, 2003• 0 citations
OpenAlex

Abstract

We show that it is NP-hard to 2nk-approximate the integral of a positive, smooth, polynomialtime computable n-variate function, for any fixed integer k. 1

Related papers

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$-variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.

arXiv:1407.1615•De Gruyter eBooks•Jul 25, 2014•22 citations

On the Hardness of Approximate Multivariate Integration

Ioannis Koutis

Lecture notes in computer science•Jan 1, 2003•2 citations

Subdeterminants and Concave Integer Quadratic Programming

Alberto Del Pia

We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by $\Delta$ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an $\epsilon$-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by $\Delta$ in absolute value. The number of these integer linear programs is polynomial in the dimension $n$, in $\Delta$, and in $1/\epsilon$, provided that the number $k$ of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with $\Delta \le 2$ and $k$ fixed. In the totally unimodular case $\Delta = 1$, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in $1/\epsilon$ and is independent of $n$, provided that $k$ is fixed.

arXiv:1810.02763•SIAM Journal on Optimization•Jan 1, 2019•8 citations

Open problems for tractability of multivariate integration

Henryk Woźniakowski

Journal of Complexity•Apr 4, 2003•15 citations

Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions

Kosuke Suzuki

arXiv:1505.02003•Journal of Complexity•Oct 18, 2016•16 citations

Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography

Alex Meiburg

Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum state tomography, we show that PSD permanents are NP-hard to approximate within a constant factor, and so admit no polynomial-time approximation scheme (unless P=NP). We also establish that several natural tasks in quantum state tomography, even approximately, are NP-hard in the dimension of the Hilbert space. These state tomography tasks therefore remain hard even with only logarithmically few qubits.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•1 citation
In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which sss-variate problems can be approximated to within ε\varepsilonε by using, say, polynomially many in sss and ε−1\varepsilon^{-1}ε−1 function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with ε−1\varepsilon^{-1}ε−1 replaced by 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of sss and 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.
We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by Δ\DeltaΔ the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an ϵ\epsilonϵ-approximate solution for this problem by solving a number of integer linear programs whose constraint matrices have subdeterminants bounded by Δ\DeltaΔ in absolute value. The number of these integer linear programs is polynomial in the dimension nnn, in Δ\DeltaΔ, and in 1/ϵ1/\epsilon1/ϵ, provided that the number kkk of variables that appear nonlinearly in the objective is fixed. As a corollary, we obtain the first polynomial-time approximation algorithm for separable concave integer quadratic programming with Δ≤2\Delta \le 2Δ≤2 and kkk fixed. In the totally unimodular case Δ=1\Delta = 1Δ=1, we give an improved algorithm that only needs to solve a number of linear programs that is polynomial in 1/ϵ1/\epsilon1/ϵ and is independent of nnn, provided that kkk is fixed.
Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum state tomography, we show that PSD permanents are NP-hard to approximate within a constant factor, and so admit no polynomial-time approximation scheme (unless P=NP). We also establish that several natural tasks in quantum state tomography, even approximately, are NP-hard in the dimension of the Hilbert space. These state tomography tasks therefore remain hard even with only logarithmically few qubits.