All Questions
598 questions with no upvoted or accepted answers
3
votes
0
answers
312
views
Linear complementarity problem: principal pivoting algorithm
I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (...
- 151
3
votes
0
answers
366
views
Amortized analysis of data structure via potential function
One common method for proving that a data structure supports an operation in $O(f(n))$ amortized time is to construct a potential function $\Phi: \mathcal S \rightarrow \mathbf R^{+}$, which ...
- 3,475
3
votes
0
answers
257
views
Oracle separating FIP for bounded-depth Frege from FIP for Frege (and hardness conditions on DDH)
Is there an oracle such that in the relativized world, bd-Frege (bounded depth Frege propositional proof system) has FIP (feasible interpolation property) but Frege does not have FIP?
Such an oracle ...
- 5,502
3
votes
0
answers
220
views
Algorithm for testing satisfiable fraction of linear equations mod 2
Hello
Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation $...
- 239
3
votes
0
answers
359
views
Do Isometry Groups Tell Us How Difficult Norms are to Compute?
The question: Consider two norms N1 and N2 on the space of n-by-n complex matrices. N1 and N2 have the same isometry group and computing N1 is NP-HARD. Does it follow that computing N2 is NP-HARD as ...
- 6,351
3
votes
0
answers
770
views
Why isn't Montgomery modular exponentiation considered for use in quantum factoring?
It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
- 15.4k
3
votes
0
answers
229
views
For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?
Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(...
- 2,442
3
votes
0
answers
538
views
Does $EXP\neq ZPP$ implies sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof:
if $EXP\...
3
votes
0
answers
318
views
Drawing a combinatorial 3-configuration of points and lines with pseudolines
This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pseudolines. Let us ...
- 784
3
votes
1
answer
77
views
Level sums, displacements: how to determine them efficiently?
Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$,
$\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$.
Define $$S(\delta,m) = ...
- 20.2k
2
votes
0
answers
95
views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
- 13.9k
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
2
votes
0
answers
93
views
How are moduli spaces related to geometric complexity theory?
I am interested in understanding the relationship between moduli spaces and geometric complexity theory (GCT).
Relation between moduli spaces and GCT:
How are moduli spaces related to geometric ...
- 29
2
votes
0
answers
71
views
Lexicographically largest incidence matrix
I have simple algorithmic question, but I can't find any source where this algorithm is explained in details.
Let's assume that we have incidence (with 0 and 1 values) matrix of size $m\times n$. Let ...
- 501
2
votes
0
answers
116
views
Reference for a coarse complexity notion
Throughout, I'm only interested in structures with domain $\mathbb{N}$, no primitive relations, and at least $0,\mathsf{Succ}$ as primitive functions. The length of $m\in\mathbb{N}$ is $\lfloor 1+\...
- 21.1k
2
votes
0
answers
173
views
NP-hardness of a string transformation problem with k templates
Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...
- 21
2
votes
0
answers
204
views
Finding specific coefficients of product of high-dimensional Fourier series faster than FFT
I need a fast algorithm to perform a specific Fourier-type computation in my physics research. Suppose I have the following two Fourier series in three dimensions
$$
a(t_1,t_2,t_3)=\sum_{j=-n}^{n}\...
- 620
2
votes
0
answers
66
views
How to check that a number probably/likely has a divisor having a specific bit length/in range?
Given a randomly generated $\alpha\in\Bbb N$ where $\alpha$ is large thus hard to factor (no small prime composites). How to check that a divisor $F\in\Bbb N$ with a specific bitlengh $n\in\Bbb N∧n<...
- 87
2
votes
0
answers
121
views
How to know if a random natural number is a probable semiprime?
Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
- 87
2
votes
0
answers
88
views
Is there a sharp phase change on circuit error rate near the error correction threshold?
(I asked this question on cstheory here, but it received no attention for four days. Hopefully it is okay to move it to mathoverflow.)
My rough intuition is that if we want to efficiently compute ...
- 1,798
2
votes
0
answers
96
views
What is the complexity / name of word search problem in linear groups?
This is a question about a search problem associated with user6976's question. Suppose we are given a finite set of elements $S \subset \mathrm{GL}_n(\mathbb{Q})$ containing inverses of all its ...
- 1,284
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
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 ...
- 13.9k
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 ...
- 51
2
votes
0
answers
201
views
On GCD and lattice reduction
$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$.
Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector.
If $GCD$ is in $NC$ and in ...
- 13.9k
2
votes
0
answers
197
views
Is orthogonal polygon with crossings count NP-complete?
The are several NP-complete problems related to the construction of orthogonal simple polygons. Rapport showed that it is NP-complete to decide the existence of orthogonal simple polygon that passes ...
- 2,993
2
votes
1
answer
877
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
- 1,171
2
votes
0
answers
44
views
Convergent algorithm for minimizing nonconvex smooth function
Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by
$$
\ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...
- 6,853
2
votes
0
answers
118
views
Computing coefficients of theta functions associated to quadratic forms
If we take an integral positive definite quadratic form $Q$ and set $\Theta_Q(z) = \sum_{k\geq 0}R_Q(k)e^{2\pi ikz}$, what are the most efficient algorithms to compute the $R_Q(k)$? I am aware e.g. of ...
- 323
2
votes
0
answers
91
views
Blind construction of planar graph with additive spanning tree count
Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
- 13.9k
2
votes
0
answers
66
views
A sub-logarithmic complexity in Analysis and N.Th
The question will be about complexity $\ \mathcal C(p)\ $ being positive and the same for all primes $\ p.$
Function $\ \mathcal Q\ $ is defined in the set of finite sequences of positive rational ...
- 4,786
2
votes
0
answers
72
views
Minimum size of a Diophantine equation detecting the emptiness of a recursive set
I have a program $P$ taking an integer as input and outputting a Boolean value. It runs in polynomial time in the length of the input.
There necessarily exists a Diophantine equation that has a ...
- 21
2
votes
0
answers
148
views
How to decide if an algebraic number is a root of a given polynomial?
Let $p$ be a polynomial with rational coefficients and $\alpha = \sqrt[n]{q}e^{i2k\pi/m}$ for some natural numbers $n,m,k$ and a rational number $q > 0$. Is there an effective algorithm for ...
- 147
2
votes
0
answers
64
views
Polynomial-time algorithm for uniformly sampling the $n$-slice of a context-free language
Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$.
Is there a polynomial-time algorithm for uniformly sampling from ...
- 21
2
votes
0
answers
159
views
Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions
playing around with stuff for my dissertation, I derived a quadratic problem in the general form
\begin{equation}
\begin{aligned}
\min_{x} \quad & x^TQx + c^Tx \\
\textrm{s.t.} \quad & Ax \leq ...
- 21
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
2
votes
0
answers
105
views
Computing bipartite matching of size $k$?
Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$?
The problem of computing all perfect matchings is #P-complete. But I ...
- 241
2
votes
0
answers
139
views
Complexity of polynomial inequalities
What is known about the complexity of deciding whether a finite set of polynomial inequalities in $n$ real variables with integer coefficients is satisfiable? Decidability is guaranteed by Tarski's ...
- 3,873
2
votes
0
answers
1k
views
what is the computational complexity of Louvain algorithm?
I am not able to find out the computational complexity of the Louvain Algorithm. Can anyone here help me? link of the paper given below:
DOI: 10.1088/1742-5468/2008/10/P10008
https://doi.org/10.1038/...
- 21
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
- 13.2k
2
votes
0
answers
70
views
Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy
The paper On graph classes with logarithmic boolean-width
claims that some graph problems are fixed parameter tractable with parameter
the boolean width.
In particular, boolean-width of the complement ...
- 25.4k
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
2
votes
0
answers
81
views
Number of solutions to linear diophantine equations, with natural coefficients in a box
Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...
2
votes
0
answers
139
views
Double Diophantine approximation
Let $0 < \alpha < 1$. For any $n$ there is a closest lower Diophantine approximation $\max p / q \leq \alpha$ with integer $0 \leq p < q \leq n$. It can be found efficiently, e.g., with Stern-...
- 5,590
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121
2
votes
0
answers
223
views
Decoding Fock spaces
Technically, the Fock space is (the Hilbert space completion of) the direct sum of the symmetric or antisymmetric tensors in the tensor powers of a single-particle Hilbert space H.(Wikipedia)
...
- 121
2
votes
0
answers
404
views
A decision problem from sheaf set theory?
Let $V^{X}$ be a sheaf model of ZF set theory, where $X$ is a topological space as it is defined in [1].
Let $T(y_1,\ldots,y_n)$ be an $B(T)$-free algebra as it is defined in [2], where $B(T)$ is the ...
- 121
2
votes
0
answers
137
views
Time complexity of randomized algorithm: right-multiplying by random elements $z_i$ from a group $H$ to achieve $H$-invariance
Note: This question was inspired by a related question about the Quantum Merlin Arthur (QMA) complexity class on Quantum Computing Stack Exchange. I was deliberating whether to ask this on CS Theory ...
- 269
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
- 21