All Questions
598 questions with no upvoted or accepted answers
1
vote
0
answers
153
views
NP-Hardness of Underdetermined Systems over $F_2$ implies the same for $F_{p^q}$
Assume that the yes-no problem of whether $x' \in F_{p^q}^{n}$ is a minimal support solution for a consistent underdetermined system $Ax=b,$ $A \in F_{p^q}^{m \times n}, b \in F_{p^q}^n$ is an NP-hard ...
- 259
1
vote
0
answers
673
views
Why are SDP generally slow?
This is more of a conceptual question. Don't expect a highly mathematical question. Nonetheless, the questions I pose here often arise in my field (not mathematics).
Usually Semidefinite Programs (...
- 345
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
0
answers
73
views
Is there any notion of a slack-matrix (and its rank) for a hyperplane arrangement?
I am assuming that the common lineality space of the hyperplane arrangement has already been factored out. So we are looking at an ``effective" arrangement in lower dimensions where all the polyhedra ...
- 2,246
1
vote
0
answers
107
views
Effective estimates for circle packing
The Riemann map from a simply connected domain to the unit disc can be approximated by circle packings thanks to a theorem of Rodin and Sullivan. (That is, take smaller and smaller triangulations and ...
- 3,383
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
1
vote
0
answers
152
views
Efficient deterministic algorithms of factorizing
My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$.
Are there such algorithms that use poly$(n, \log q)$ bit operations?
I know ...
- 2,576
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
1
vote
0
answers
129
views
Analogues of Specker sequences for different complexity classes
Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...
- 1,155
1
vote
0
answers
139
views
bounded degree graph colouring.
I was wondering if anyone could provide references on the following:
Is determining the chromatic number of a bounded degree graph APX-complete?
2.I've seen the result that states it is NP-hard to ...
- 903
1
vote
0
answers
90
views
Calculation of cardinality of Jacobians
The problem of calculation the number of rational points on curves over finite fields is $\#P$-complete - "Counting curves and their projections".
Is it true for calculation of number of rational ...
- 2,576
1
vote
0
answers
28
views
The complexity of Max-K interval selection
I came up with the following problem, but do not know how to analyze it.
Let $S$ be an ordered set of integers with size $n$ (i.e., $S=\{1,2,...,n\}$). An interval $INV(a,b)$ covers the elements in $...
- 11
1
vote
0
answers
34
views
Some confusion regarding the definition of NPO reduction
I've seen the following definition in a paper on approximation preserving reductions.
Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} \pi_{...
- 213
1
vote
0
answers
144
views
On variant of integer factorization
In the post on site cstheory.stackexchange on whether a variant of integer factorization
$$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ ...
- 13.9k
1
vote
0
answers
203
views
A reference for "Borel Sets and Circuit Complexity"
Is there any pdf version of M.Sipser's "Borel Sets and Circuit Complexity" or , since I am unable to get this paper, is there other reference closely related to theory in that paper?
- 51
1
vote
0
answers
41
views
Complexity of finding algebraic dependency of polynomials over the rationals or in a finite field?
Let $f_1,\ldots f_m \in K[x_1,\ldots,x_n]$ where $K$ is $\mathbb{Q}$ or a finite field.
Q1 What is the complexity of finding all algebraic dependencies between $f_i$?
Q2 What is the complexity of ...
- 25.4k
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
1
vote
0
answers
112
views
Canonical representation of binary decision trees in Ptime?
I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence.
More ...
- 111
1
vote
0
answers
171
views
Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?
In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far).
What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0
answers
138
views
FPTAS for approximating the permanent of a matrix
My question concerns approximating permanent of an $n$-by-$n$ matrix.
Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...
- 11
1
vote
0
answers
164
views
What's the complexity of the one sink directed subgraph isomorphism problem?
I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...
1
vote
0
answers
128
views
Reducing enumeration of reduced words in general Coxeter groups to another #P-complete problem
There is a polynomial time algorithm that takes as inputs a Coxeter system $(W,S)$ with $S$ finite (but with $W$ not necessarily finite), say encoded as a Coxeter matrix, as well as two reduced words ...
- 2,168
1
vote
0
answers
82
views
Recognizing bridgeless cubic graph with special 2-factor
A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a perfect matching).
I conjecture ...
- 2,993
1
vote
0
answers
140
views
Reduce a Combinatorial problem
It is given n sets with k vectors. (k is element-wise positive or zero)
Choose one vector of each set so that the biggest element of the sum of the chosen vectors is minimal.
What i also know but is ...
- 11
1
vote
0
answers
68
views
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
polynomial ...
- 25.4k
1
vote
0
answers
115
views
What is the generic complexity of First Order Predicate Calculus?
I suspect that it should be the same as that of the Turing machine halting problem, which wikipedia gives as GenP and attributes this result to Hamkins and Miasnikov, but I am not sure. Is the generic ...
- 111
1
vote
0
answers
74
views
TSP: Approximation Ratio of the Double Tree Heuristic after Diagonals have been Removed
In their article "Double-Tree Approximations for the Metric TSP: Is the Best One Good Enough?", Vladimir Deineko and Alexander Tiskin derive a lower bound for the approximation ratio of the double-...
- 13.2k
1
vote
0
answers
75
views
Are there any known bounds on the value of solutions of linear integer programming?
Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints?
...
- 111
1
vote
0
answers
493
views
Complexity of Nested Linear Optimization
My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint:
$$\max(\...
- 13.2k
1
vote
0
answers
157
views
Indecomposability of image transformations (pure algebra). Open questions
W-transformations -- definitions
We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...
- 7,500
1
vote
0
answers
196
views
Interior point optimisation using big M for L1 norm on linear system using Dikin's Affine method
I am a 4th year undergrad surveying student studying computations, specifically $L_{1}$ norm minimisation of residuals in large data sets. To start with (and probably to finish with) I'm using a set ...
- 111
1
vote
0
answers
256
views
Equal maximum and minimum in a large-scale linear programming
For a linear optimization of an integral (with integral constraints), I perform a linear programming for the equivalent series. Maximum and minimum of the LP problem tend to be equal as I increase the ...
- 111
1
vote
0
answers
111
views
Schönhage's SMM with only one instruction
It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
1
vote
0
answers
145
views
Are set covering problems with nonlinear cost functions NP-Hard?
Are set covering problems (set cover problem wikipedia) with a nonlinear cost function also NP-hard? Is there a general result about this?
To be more specific the cost function I am interested in ...
1
vote
0
answers
126
views
Matrix Minimax problem
I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The $M_k$...
- 4,829
1
vote
0
answers
112
views
Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?
Did anybody come across a computational problem which is related to the notion of cartesian product and is at least NP-hard?
Equally interesting would be to learn about such problems with a non-...
- 41
1
vote
0
answers
89
views
Deciding / Approximating Parity of Small Depth Decision Trees
Let C be a circuit such that:
C: $\{0,1\}^n$ to $\{0,1\}$
the top most gate is a parity gate
all the inputs to the parity gate are small depth decision trees
there is a total of $2^{ log^k n}$ ...
- 45
1
vote
0
answers
628
views
Totally unimodular Matrices
A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
- 11
1
vote
0
answers
266
views
Multiobjective semidefinite programming
Let $C$ be size $n \times n^{2}$.
Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.
There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$.
$B$ is ...
- 800
1
vote
0
answers
1k
views
How to solve simple bilinear equations under extra linear constraints
Hello,
This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:
$\lambda_i^T u_{...
- 53
1
vote
0
answers
538
views
Representing vertices of a cube using linear combination of tensor product of smaller cubes
Let $n,N \in \mathbb{N}$ with $N \ge n^{2}$.
Let $F[i] = \square[i]$ refer to the cube which has vertices from $\{-1,0,1\}^{n^{i}}$ ($n^{i}$ tuple of alphabets from $\{-1,0,1\} = \square[0] = F[0]$)
...
1
vote
0
answers
228
views
Inherent complexity of a language --- when does it exist?
For a language $L$, you can talk about the complexity of a Turing machine $M$ which decides $L$. Can you talk about the time complexity of the language $L$ itself, i.e. say $L$ has complexity $f(n)$ ...
- 3,475
1
vote
0
answers
117
views
Formal Definition of Random Reducibility
What is the formal definition of Random Reducibility>
Arora/Barak is like:
"yeah, so it's kind like you take an instance of a problem, create n random instances of the problem; and if you have the ...
- 11
1
vote
0
answers
357
views
Is this minimization problem NP-Complete ?
We are given an $n\times (n+k)$ matrix $A,$ with entries in $\mathrm{GF}(2),$ of the form $A=(I_n|B)$ where $I_n$ is a $n\times n$ identity matrix where the matrix $B$ has no "zero" rows or columns.
...
- 209
1
vote
0
answers
376
views
NP-complete variants of NPI problems
Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
- 2,993
1
vote
0
answers
638
views
Expected value of sum of fractions
Suppose $r$ is a set of attributes with probabilities while $p$ is a set of attributes without probabilities. For example, say that $r$ = {$a$:0.4, $b$:1.0} and $p$ = {$a$, $c$}. (Here, $a.prob = 0.4$ ...
- 21
1
vote
0
answers
282
views
Complexity of a problem related to 3D matching?
Given a set of triples of a base set $S$, find a subset of triples such that each element in $S$ appears exactly in one triple. This problem is NP-complete by reduction from NP-complete problem 3D ...
- 2,993
1
vote
0
answers
259
views
Self-improvement property of optimazation problems?
Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ...
- 2,993