Skip to main content

All Questions

Filter by
Sorted by
Tagged with
6 votes
2 answers
1k views

MIP*=RE theorem and its impact on logic and proof theory

In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
truebaran's user avatar
  • 9,330
1 vote
0 answers
51 views

Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed. With the two (related) examples, it is clear that ...
Ro. Cohof's user avatar
1 vote
0 answers
67 views

Are the lower elementary functions closed under limited recursion?

The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
Guozhen Shen's user avatar
  • 1,782
1 vote
0 answers
145 views

Complexity of calculating the expectation of $\operatorname{Tr} h(A)$, $A$ is a random matrix

$A$ is a $d_1\times d_1$ random matrix. Given $\{g_i\}~(1\leq i\leq n)$ iid Gaussian variables, $f_{ij}(g_1,g_2,...,g_n)~(1\leq i,j\leq d_1)$ are degree-$d_2$ polynomials. And $f_{ij}\equiv f_{ji}~(\...
qmww987's user avatar
  • 91
1 vote
0 answers
94 views

Linear Program Optimal Value

If $f(A,b,c)$ is the optimal value of a linear program $\min c.x$ subject to $A.x \leq b ; x \geq 0.$ Does $f(A,b,c)$ have a piecewise polynomial/rational upper bound in $(A,b,c)$ on the domain of ...
Pathikrit Basu's user avatar
0 votes
1 answer
114 views

Mixed integer program and continuous Diophantine approximation

Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem. $$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$ subject to ...
Pathikrit Basu's user avatar
15 votes
1 answer
1k views

(Very) Large numbers, Chaitin's incompletness theorem and a specific upper bound

Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>...
truebaran's user avatar
  • 9,330
2 votes
1 answer
174 views

Optimization over permutation

The Problem This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
Honglian's user avatar
1 vote
0 answers
114 views

Computing sine of gamma function [closed]

In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step? Is there a ...
roignoirewg's user avatar
2 votes
1 answer
240 views

Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
Makogan's user avatar
  • 123
1 vote
0 answers
35 views

Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?

I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
seed's user avatar
  • 111
0 votes
0 answers
61 views

On diagonalizations over complexity classes

I am looking for the following PhD thesis, but could not find it, and all my attempts for finding it failed. I am wondering if there is a way to get it: On diagonalizations over complexity classes By: ...
Mohammad Golshani's user avatar
0 votes
0 answers
55 views

Relationship of optimal solutions between the total function and the sub function

This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
lzzz's user avatar
  • 1
0 votes
0 answers
85 views

Show that $\max_{P_X : X\in (0,1) } \left| \frac{\mathbb{E} [ f'(X) ]}{ \mathbb{E} [ f(X) ] } \right|$ is maximized by at most two mass points

Let $f$ be some given well-behaved function. Consider the following optimization problem overall probability distribution on $[0,1]$ \begin{align} \max_{P_X : X\in [0,1] } \left| \frac{\mathbb{E} [ ...
Boby's user avatar
  • 671
2 votes
1 answer
46 views

Complexity for determining whether a given metric space is hyperconvex?

Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex? Definition: A metric space is said to be hyperconvex if ...
pyridoxal_trigeminus's user avatar
1 vote
1 answer
69 views

$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance

Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
user2512443's user avatar
6 votes
0 answers
151 views

Complexity of continued fraction arithmetic operations

Let $A = [a_0; a_1, \dots]$ and $B = [b_0; b_1, \dots]$ be continued fractions. Let's say that we want to compute $A+B$ or $A \cdot B$ while staying in the continued fraction representation. So, for ...
Oleksandr  Kulkov's user avatar
2 votes
1 answer
125 views

The counterpart of productive set with polynomial computational complexity

For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...
XL _At_Here_There's user avatar
3 votes
1 answer
807 views

Language equivalence between deterministic and non-deterministic counter net

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
Lionheart's user avatar
8 votes
1 answer
454 views

Classes of groups with polynomial time isomorphism problem

It is known that the isomorphism problem for finitely presented groups is in general undecidable. What are some classes of groups whose isomorphism problem is known to be solvable in polynomial time? (...
Mithrandir's user avatar
1 vote
1 answer
119 views

Optimization on non-convex set

Let $\Omega$ be an open bounded subset of $\mathbb{R}^2$ and $f\in L^2(\Omega)$ be a given function. Consider the optimization problem $$\mathrm{min} \int_\Omega u(x) f(x) \,dx\,,$$ where a minimum is ...
mlogm's user avatar
  • 11
-3 votes
1 answer
531 views

Counter net decidability [closed]

Let one Deterministic Counter Net ($\mathrm{1DCN}$), which is a finite-state automata where every state is complete means all states has transition of all input symbols and their respective weight ...
Lionheart's user avatar
5 votes
0 answers
180 views

Is the matrix multiplication exponent $\omega$ independent from the choice of the base field

The matrix multiplication exponent, usually denoted by $\omega_{F}$, is the smallest real number for which any two $n\times n$ matrices over a field $F$ can be multiplied together using ${\...
Nick Chen's user avatar
  • 151
10 votes
1 answer
518 views

Can $N!$ be computed in less than $\mathcal{O}(N)$ operations?

The standard algorithm to compute the factorial function $N!$ via repeated multiplications has complexity $\mathcal{O}(N)$, in the model in which each operation costs 1, no matter how many digits the ...
user6873235's user avatar
1 vote
0 answers
34 views

Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?

Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$ $$ax+by=c.$$ Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
Turbo's user avatar
  • 13.9k
0 votes
2 answers
530 views

Any idea of solving an optimization problem with cubic constraints?

I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem? $$ \begin{array}{ll} \underset {y, z} {\...
Erik's user avatar
  • 21
1 vote
0 answers
101 views

On determinant and permanent of certain homotopy defined simple matrices

Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$ $$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$ hold ($per$ refers to permanent). I. What ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
161 views

On an optimization question

Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ ...
Turbo's user avatar
  • 13.9k
0 votes
0 answers
304 views

A question regarding an unprovability proof

Let LA denote polynomial time arithmetic, Con_LA the equation stating the consistency of LA, LAJ the system LA+Con_LA, and E2A double exponential time arithmetic. A manuscript of mine provides a proof ...
Martin Dowd's user avatar
0 votes
0 answers
146 views

Maximizing the norm of a sum of Hermitian matrices

Consider the following problem: Problem: Given $n\times n$-Hermitian matrices $A_1,\dots,A_r$, find $e_1,\dots,e_r\in\{-1,1\}$ such that $\|e_1A_1+\dots+e_rA_r\|_\infty$ is maximized. Here the norm is ...
Joseph Van Name's user avatar
1 vote
1 answer
201 views

Diagonally dominant matrix via rows permutation

Diagonally dominant matrices are required in many linear algebra algorithms such as the Gauss-Seidel algorithm. Some matrices can be made diagonally dominant by permuting its rows and others cannot. ...
Mohammad Al-Turkistany's user avatar
1 vote
0 answers
223 views

Fastest algorithm for finding the closest semi-definite matrix?

Given a real-valued, symmetric matrix $A \in \mathbb{R}^{n \times n}$, I'm interested in finding the closest positive semi-definite matrix $X^*\in \mathbb{R}^{n \times n}$: $$ X^* = \mathop{\text{...
Alec Jacobson's user avatar
1 vote
0 answers
61 views

Is there any lower bound for basis computation in finite Abelian groups?

Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite ...
Vasac's user avatar
  • 11
1 vote
0 answers
56 views

Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?

Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...
Yossi Peretz's user avatar
2 votes
0 answers
221 views

Modular inverse computation - avoiding Euclidean algorithm

Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime. If we already know ...
Turbo's user avatar
  • 13.9k
1 vote
2 answers
121 views

How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

I am looking for an algorithm to solve the following optimization problem $$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$ where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$. ...
user3750444's user avatar
5 votes
0 answers
129 views

Finding an $\mathbb{F}_q$-point on one specific intersection of quadrics

Let $\mathbb{F}_q$ be a finite field of large characteristic and $a_1, a_2, \cdots, a_n \in \mathbb{F}_q$ be some pairwise different elements. I assume that $\sqrt{-1} \in \mathbb{F}_q$. Consider the ...
Dimitri Koshelev's user avatar
3 votes
0 answers
105 views

Techniques for solving linear inequalities

For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...
Dmitry's user avatar
  • 231
0 votes
1 answer
103 views

Constrained linear optimization problem on $C^1$

I am dealing with a problem of the form ($a<b$) $$ \displaystyle \max_{v \in C^1([a, b])} \int_a^b v(x)~\mathrm{d}x, \quad \mathrm{s.t.} \int^b_a \big(-o'(x)v(x)-v'(x)o(x)\big)f(x)~\mathrm{d}x \...
Hyperbolic PDE friend's user avatar
1 vote
1 answer
474 views

Is non-convex optimisation really in NP class?

Crossposted on Mathematics SE I've seen in many optimisation papers the statement that general non-convex optimisation problem is NP-hard. If we assume that non-convex optimisation is in NP class, it ...
Dmitry Vilensky's user avatar
1 vote
0 answers
36 views

Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?

Suppose that $P$ is a polyhedron represented by $$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$ and $P$ contains interior points. Moreover, the ...
ZZZZZZ's user avatar
  • 33
2 votes
0 answers
245 views

Pancake sorting problem – Is computing f(n) NP-hard?

The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems: MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
borekking's user avatar
3 votes
1 answer
332 views

Complexity of inverting and multiplying against a symmetric Toeplitz matrix with two repeated entries

I know that the computational complexity of inverting a general $n \times n$ matrix $A$ is $O(n^{2.373})$ and multiplying it against an $n \times m$ matrix is $O(n^2m)$. Moreover, I've seen that ...
Annie's user avatar
  • 91
2 votes
2 answers
235 views

Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?

Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$ a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$. Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=...
user3020699's user avatar
0 votes
0 answers
145 views

Bound on solutions of $Ax \ge b$

Let $A \in \mathbb{Z}^{m \times n}, b \in \mathbb{Z}^{m \times 1}$. One can show that if there is a solution of $Ax \ge b, x \in \mathbb{R}^n$ then there is one such that $\|x\|_{\infty} \le c (\|A\|_{...
user1868607's user avatar
0 votes
0 answers
59 views

NC0 randomness vs. non-uniformity

In Ajtai and Ben-Or. A theorem on probabilistic constant depth Computations. STOC '84, 1984 Ajtai and Ben-Or show a non-uniform derandomization of BPAC0. Is there a similar relation known for ...
user499408's user avatar
8 votes
0 answers
360 views

Worst-case complexity of calculating homotopy groups of spheres

Is the best known worst-case running time for calculating the homotopy groups of spheres $\pi_n(S^k)$ bounded by a finite tower of exponentials? How high is a tower? Does $O(2^{2^{2^{2^{n+k}}}})$ ...
Joe Shipman's user avatar
0 votes
0 answers
84 views

1-degree SOS proof refutes Linear Programming

I am trying to understand Sums-of-Squares proof systems. A degree $d$ Sums-of-Squares refutation for a set of polynomial equations $P = \{p_1(x) = 0, ..., p_m(x) = 0\}$ is defined as $\sum_{i=1}^m g_i(...
Tom Keaton's user avatar
1 vote
1 answer
119 views

Adding linear constraint to the domain

I don't know if it is a well-known problem, but I have been struggling to come up with an algorithm. I have a set of linear constraints $Ax\le b$, $b\ge 0$ ($b$ and $A$ are given, $x$ is a variable). ...
Ryszard Eggink's user avatar
1 vote
0 answers
96 views

On optimizing a multivariate quadratic function subject to certain conditions

The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
shahulhameed's user avatar

1 2
3
4 5
37