All Questions
598 questions with no upvoted or accepted answers
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}~(\...
- 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 ...
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 ...
- 111
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$ ...
- 13.9k
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 ...
- 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]$ ...
- 13.9k
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{...
- 723
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 ...
- 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\...
- 21
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 ...
- 33
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)$ ...
- 61
1
vote
0
answers
336
views
Closed-form solution of a particular linear program
(Note: I asked a similar question at math.stackexchange but the present one is more precise.)
I have a linear program of the form:
$$\text{minimize} \space\space x_1 \space\space \text{subject to:}$$
$...
- 1,000
1
vote
0
answers
70
views
Is this factorization problem in EXP?
Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $...
- 13.9k
1
vote
0
answers
46
views
Computational hardness of a discrete generalized rectangle packing problem
I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (...
1
vote
0
answers
47
views
Nash Equilibria change linearly in (some) game parameters. Already known / follows from a more general result?
EDIT: The key thing that I am wondering about is the linearity of the P2 strategy, not the constancy of P1. (The latter is straightforward.)
Question: Is the following result already known? Or is it a ...
1
vote
0
answers
121
views
Frog game on tree graphs is in NP but not in P (NP-complete)?
Problem
We can restrict ourselves to tree graphs. What is the complexity of the following problem?
Let $G$ be simple connected graph with vertices in $V$, edges in $E$, and a vertex weighted function $...
- 611
1
vote
0
answers
123
views
Finding the optimal arithmetic circuit for evaluating a given polynomial
The Horner's algorithm takes as input a univariate polynomial $f(X)$ and an evaluation point $x$ and computes $f(x)$ using $O(\deg(f))$ field operations.
Suppose now that the polynomial $f(X)$ is ...
- 297
1
vote
0
answers
59
views
How do I incorporate Ito's lemma into the solution for a finite-horizon stochastic cake-eating problem?
I'm interested in finite-horizon, continuous-time cake-eating problems in which the agent has a time-horizon $W$ over which to eat the cake, and then chooses an optimal consumption path $\{h_t\}_0^W$, ...
- 11
1
vote
0
answers
42
views
If statement in the algebraic group model (AGM)
In the algebraic group model (https://eprint.iacr.org/2017/620.pdf), can one use "if" statement? For example, can one do the following in AGM?
input: x, y, z
if (x = y) then z = x else z = ...
- 651
1
vote
0
answers
92
views
Formalizing intuition of search hardness
Basically, this is a search problem of an object that is promised to exist. Suppose we have an object that can be described completely and uniquely by $m$ properties (each n bits). Suppose a search ...
- 2,993
1
vote
0
answers
42
views
What is the complexity of the matrix multiplication closure for a given generating system?
Given a generating set of $k$ matrices $X = \{M_1, M_2, \ldots, M_k\}$, with $M_i\in \mathrm{Mat}(\mathbb{C},n)$, what is the worst case complexity for computing the algebraic closure w.r.t. matrix ...
- 21
1
vote
0
answers
101
views
Fast algorithm to compute nimber product
It is known that nimbers (Grundy numbers) below $2^{2^n}$ form a field with the nim addition $\oplus$ and the nim product $\cdot$.
Generally, one can develop an algorithm to compute the product of two ...
- 1,171
1
vote
1
answer
331
views
Finding a special solution in a solution set over F2
Given a solution set of a linear system of the following form
$$
\{ \begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...
- 51
1
vote
0
answers
61
views
Linear programming robustness to input perturbations
I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...
- 11
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 287
1
vote
0
answers
35
views
How to chose the start vector for the MTZ variables
In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
- 13.2k
1
vote
0
answers
69
views
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.
MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
- 13.9k
1
vote
0
answers
181
views
Does fraction-free Gaussian elimination use fractional row operations?
I would like to understand whether Gaussian elimination of an integer matrix, which uses only row operations of the form
Addition (or subtraction) of row $i$ to row $j$
can be performed in ...
- 111
1
vote
0
answers
58
views
Second-order envelope theorem for linear programming
Consider parameterized linear programming $V(\theta) = \max_x \langle c(\theta),x\rangle$ s.t. $A(\theta)x\leq b(\theta)$, $x\geq 0$. Let's also assume $c,A,b$ are infinitely differentiable with ...
- 373
1
vote
0
answers
37
views
Sum of all integer binary solutions of a TUM linear system
I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
- 11
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
- 25.4k
1
vote
0
answers
583
views
Langlands program and complexity theory
Back when I was an undergraduate, I spent some time reading the about the modularity conjecture, but the details are fuzzy now.
One of the motivations I imagined for the Langlands program was for ...
- 59
1
vote
0
answers
75
views
Subgraph isomorphism problem with linear map
I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:
Problem 1: Given two graphs $G=(V, E)$ ...
- 101
1
vote
0
answers
25
views
Reporting uncoverable directed simple cycles in digraphs
What is known about cycles in digraphs that can't be member of any of that digraph's vertex disjoint directed cycle covers as illustrated below?
in that "cat's eye graph" the green cycle ...
- 13.2k
1
vote
0
answers
46
views
Computational complexity of rate $\frac{1}{2}$ codes
We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing the minimum distance of a (binary)...
- 71
1
vote
0
answers
118
views
Promise version of minimum distance
It has been known for some time that computing minimum distance of a linear code (minimum weight codeword) is NP-hard.
This immediately also says that given a code $C$, calculating minimum hamming ...
- 71
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
1
vote
0
answers
209
views
Solution to system of linear equations
Input: System of linear equations $$A[x_1,\dots,x_{t}]=b$$ where number of equations is at least number of variables but independence is not guaranteed. However there is atmost one non-negative ...
- 13.9k
1
vote
0
answers
122
views
Integrality of polyhedra
Given two polyhedra in $H$ representation $P_1:Ax\leq b$ and $P_2:Bx\leq c$ which are integral are bounded when is their intersection also integral?
Given two polyhedra in $H$ representation $P_1:Ax\...
- 13.9k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
- 13.2k
1
vote
0
answers
172
views
continuity of linear programming
I have the following conjecture:
Given a closed convex set $S \subseteq \mathbb{R}^n$ and one of its exposed face $F=\{x \in S \mid \pi x = \pi_0\}$, where $\pi x =\pi_0$ is the supporting hyperplane ...
- 37
1
vote
0
answers
920
views
Maximizing a piecewise-linear convex function
Crossposted on Operations Research SE.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:
...
- 111
1
vote
0
answers
62
views
Complexity of checking if a set is an additive basis
A set of nonnegative integers $A$ is said to be an additive basis of order $k$ if every nonnegative integer is equal to the sum of $k$ elements of $A$. For example, Lagrange's theorem says that the ...
- 71
1
vote
0
answers
323
views
Decomposition of Polyhedral - An example
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
- 111
1
vote
0
answers
78
views
$\mathsf{NP}$ complete version of Skolem arithmetic
Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities.
...
- 13.9k
1
vote
0
answers
176
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k
1
vote
2
answers
267
views
Optimal path with multiple costs
Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...
- 367
1
vote
0
answers
47
views
Restriction of Rademacher Complexity
Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...
- 5,405