Skip to main content

All Questions

598 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers
90 views

Computing basis of a lower set given basis of complementary upper set

In a poset $P$, $U\subseteq P$ is an upper set when for all $x\in U$, we have $y\ge x$ implies $y\in U$. Any subset of $P$ generates an upper set, and the basis of an upper set $U$ is the smallest ...
Mike Earnest's user avatar
2 votes
0 answers
265 views

Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here. I want to know the optimal complexity of an algorithm (I mean the ...
user39115's user avatar
  • 1,805
2 votes
0 answers
190 views

Existence of roots of high order polynomial over finite fields

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...
Paul's user avatar
  • 509
2 votes
0 answers
461 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
joro's user avatar
  • 25.4k
2 votes
0 answers
609 views

Is finding a single vector in the null space as difficult as discovering the whole null space?

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is: Is the ...
Yuan Gao's user avatar
  • 163
2 votes
0 answers
131 views

characterization of all periodic tiling of a simple set of Wang Tile

Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set. Now, I wish to characterize all the periodic tilings of this set (better if they are ...
user40780's user avatar
  • 867
2 votes
0 answers
91 views

Algorithms to find the solutions of a homogenous matrix equations for non-commutative rings

In one paper from 1980 I found a note that there are no known algorithms for solving homogenous matrix equations $x \cdot M = 0$ for matrices which elements belong to a non-commutative ring. (The non-...
Leonid Dworzanski's user avatar
2 votes
0 answers
163 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
user40780's user avatar
  • 867
2 votes
0 answers
120 views

integrality of a linear program -- binary equality constaints

Consider the following linear program: $\left\{ \begin{array}{l} \underset{x}{max} \;\;c^Tx\\ [I, \;B]x = \mathbf{1}\\ x\geq 0 \end{array} \right.$ where $c$ is a vector ...
Ali's user avatar
  • 127
2 votes
0 answers
152 views

Reference Request: Properties of the Integer Factorization Polytope

The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online here:...
Manfred Weis's user avatar
  • 13.2k
2 votes
0 answers
250 views

cyclotomic polynomials of given degree

Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute ...
Igor Rivin's user avatar
  • 96.4k
2 votes
0 answers
146 views

Odds of projections of a point not on the hyperplane

Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane. Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$. Let $\...
Turbo's user avatar
  • 13.9k
2 votes
0 answers
179 views

Kolmogorov complexity proof of Lovasz local lemma

Roughly speaking, the Kolmogorov Complexity proof of Lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, ...
tap1cse's user avatar
  • 69
2 votes
0 answers
39 views

In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?

I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
Craig's user avatar
  • 21
2 votes
0 answers
163 views

existence of lattice point in polytope

This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
Alex's user avatar
  • 501
2 votes
0 answers
63 views

Put positive polynomial in finite intersection of half-spaces

This is a cross-posting of a MSE question (which did not attract any attention there so far). Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...
Ewan Delanoy's user avatar
2 votes
0 answers
128 views

supersingular curve detector

Suppose I give you a prime $p$ and ask for a non-CM supersingular elliptic curve over $\mathbb{F}_p.$ Can this be done in polynomial time (so, polynomial in $\log p$)?
Igor Rivin's user avatar
  • 96.4k
2 votes
0 answers
179 views

Randomized alternative to Buchberger's algorithm

Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra. Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...
user19172's user avatar
  • 529
2 votes
0 answers
230 views

Consistency of a system of linear equations

I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
Star's user avatar
  • 221
2 votes
0 answers
917 views

Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
Alex R.'s user avatar
  • 4,952
2 votes
0 answers
120 views

Circuits by Level

Context: googling existing results on Circuit Complexity. I'm aware there are classes like AC, ACC, TC, NC, etc.. Now, suppose I have a circuit, it has the following additional program: The circuit ...
circuits2's user avatar
2 votes
0 answers
215 views

Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right), $$ where all $c_{ij}<0$ (so that ...
Ben's user avatar
  • 567
2 votes
0 answers
642 views

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of rectangular ...
Grzegorz Jaśkiewicz's user avatar
2 votes
0 answers
123 views

IP[poly] vs AM[poly]

I know the following: $$IP[k] \subseteq AM[k+2]$$ Now, I also know that $$ \\#SAT_D \in IP[poly]$$ (As shown on page 159 of Arora/Barak). In their proof, (and the following proof of $$ TBQF \in ...
pspace's user avatar
  • 21
2 votes
0 answers
227 views

Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs?

Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex ...
Mohammad Al-Turkistany's user avatar
2 votes
0 answers
535 views

Undecidability, Church Turing Thesis, and P/poly

I find the following three facts individually acceptable, but together deeply unsettling: 1) P/poly can decide the unary language $\{ 1^n | M_n(n) \quad \text{halts} \}$ via advice string. 2) Church ...
2 votes
0 answers
143 views

finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply. Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...
Yaroslav Bulatov's user avatar
2 votes
0 answers
289 views

Finding globally minimal row subsets of an integer matrix which generate the full row span

Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$. Given a subset of the rows of $A$ it is ...
Max Horn's user avatar
  • 5,654
2 votes
0 answers
313 views

Complexity of a variant of the Mandelbrot set decision problem?

This is a modified version of a question posted on StackExchange TCS. Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define $M=${$(c,k,r)...
Mohammad Al-Turkistany's user avatar
2 votes
0 answers
281 views

Recovering a piecewise affine function

Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible: Computing $f(x_1,x_2)$. Computing a subgradient to $f$ at $(x_1,x_2)$ Computing all ...
Ben's user avatar
  • 567
2 votes
0 answers
637 views

What effect would a proof of P≠NP have on the field of complexity theory?

This question is motivated by Scott Aaronson's comment about his bet: "If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it." http://...
user8232's user avatar
2 votes
0 answers
5k views

A system of linear equations with linear constraints

Mathematical problem. Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\...
Florian Breitwieser's user avatar
1 vote
0 answers
61 views

Reference request: Proof theory in $W_1^1$

Buss defined $V_2^1$​ as a second-order bounded arithmetic corresponding to $\mathsf{PSPACE}$. Later, Skelley introduced $W_1^1$​, a third-order bounded arithmetic of $\mathsf{PSPACE}$. Since the ...
palala's user avatar
  • 11
1 vote
0 answers
29 views

Integral hull of a polyhedron Q is polyhedron

Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
Sowbarnika R's user avatar
1 vote
0 answers
37 views

Computing all roots of a function with square-root terms

Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function $$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$ Can we find all the ...
Abheek Ghosh's user avatar
1 vote
0 answers
114 views

Simultaneous elimination of variables in multiple polynomials

I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
92 views

Proof for non-existence of short integer program for squares

We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question. Is there a way to show within an ...
Turbo's user avatar
  • 13.9k
1 vote
0 answers
69 views

Is it in theory possible to perform general Miller’s algorithm inversion as used with the optimal ate pairing with large trace in subexponential time?

Let’s I have the following : 2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their ...
user2284570's user avatar
1 vote
0 answers
99 views

Minimum of the maximum element frequency given the family size and the universe size

[Crossposted at math.stackexchange]. Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$. I have written and solved ...
Fabius Wiesner's user avatar
1 vote
0 answers
50 views

Computational complexity of deciding if two elements are in the same cycle of a permutation, version 2

This question has relation with this previous one, although the two cases are not likely solved with the same method. Let us consider a function $P:\{0,1\}^*\to\{0,1\}^*$ that can be calculated in ...
Doriano Brogioli's user avatar
1 vote
0 answers
68 views

Primality testing by reversible computation using the prime number theorem

Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
user1747134's user avatar
1 vote
0 answers
87 views

complexity of membership problem in finite general linear group

Suppose $G$ is a subgroup of $GL(n,q)$ given by a list of generators. What is known about the complexity of the corresponding "membership problem", that is, the problem of deciding whether a ...
Pierre's user avatar
  • 2,287
1 vote
0 answers
126 views

Integration in polynomial time

The work of Friedman and Ko and Müller guarantee the polynomial time computability of the integrals of analytic functions inside the circle of convergence. But do algorithms have practical value? Is ...
poeaqnwgo's user avatar
1 vote
0 answers
171 views

Fast algorithm for computing certain signal transformations

Let $f,g,h:\mathbb Z\to\mathbb C$ supported on $[-n,n]$.  For $\tau\in \mathbb Z$, let $\operatorname{sh}_\tau f$ be the shift of $f$ by $\tau$ (i.e. $(\operatorname{sh}_\tau f)(t) = f(t-\tau)$). ...
Rami's user avatar
  • 2,639
1 vote
0 answers
49 views

Computing geodesic length of Euclidean lines in the manifold of positive definite matrices

I am working with the manifold of positive definite matrices $PD(n)$ equipped with the affine-invariant Riemannian metric (AIRM) $g_P(V,W):=tr(P^{-1}VP^{-1}W)$, where $P \in PD(n)$ and $V,W \in T_P PD(...
Spencer Kraisler's user avatar
1 vote
0 answers
168 views

Circulant matrix inverse in $GF(p)$

For a polynomial $C(x)=c_0+\dots+c_n x^n$, consider a circulant matrix $C$ such that $$ C= \begin{pmatrix} c_0 & c_{n-1} & \cdots & c_2 & c_1 \\ c_1 & c_0 &...
Oleksandr  Kulkov's user avatar
1 vote
0 answers
52 views

Complexity of the TSP for hypercube graphs

Question: what is known about the complexity of finding the Hamilton cycle of minimum weight in graphs that resemble hypercubes with weighted edges?
Manfred Weis's user avatar
  • 13.2k
1 vote
0 answers
116 views

Sudden drop in complexity class due to the more general correlations

Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
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
5 6
7
8 9
12