**1**

vote

**0**answers

21 views

### Bit complexity versus arithmetic complexity of polynomial multiplication

Given degree $d_1$ and $d_2$ polynomials in $\Bbb Z[x]$ with coefficient sizes of bits $b_1$ and $b_2$ respectively
(1) what is the bit complexity of multiplying the two polynomials?
(2) What is ...

**0**

votes

**0**answers

10 views

### Approximation preserving reductions

I've seen in the following document
https://hal.archives-ouvertes.fr/hal-00958028/document
A definition of the $\leq_{S}$ reduction defined specifically for minimisation problems at the bottom of ...

**4**

votes

**0**answers

64 views

### Complexity of approximating the size of the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$
It is NP-hard to compute $S_M$ exactly I believe by applying the ...

**2**

votes

**1**answer

46 views

### Complexity of counting MAXCUT in planar graphs — seemingly contradicting claims

Confusion is likely. Appears to me two papers give contradicting claims
about the complexity of counting MAXCUT in planar graphs.
Exact Max 2-SAT: Easier and Faster p. 6
However, counting the ...

**6**

votes

**2**answers

191 views

### Variation on the Subset Sum Problem

Given a nonempty set of integers, and given that there exists a subset of this set whose elements sum to zero, is finding the smallest such subset NP-complete?
Disclaimer: The above question ...

**4**

votes

**1**answer

168 views

### Polynomial factoring over finite fields

What is known in general about the complexity of factoring polynomials over finite fields?
For instance given $\Bbb F_q$ where $q=p^n$ and total degree $d$ polynomial in $m$ variables what can we say ...

**1**

vote

**0**answers

23 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} ...

**3**

votes

**1**answer

87 views

### Weak Bounded Arithmetics

Let $\Sigma^b_i$ and $\Pi^b_i$ formulas be bounded formulas defined by Buss in language of $L_b$. $PIND(\phi(x))$ is the formula:
$$\phi(0)\land \forall x(\phi(\left \lfloor \frac{x}{2} \right ...

**1**

vote

**1**answer

72 views

### $0/1$ programming multiple quadratic constraints

If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time.
If we have an $n$-variable degree $2$ system how many constraints ...

**2**

votes

**0**answers

9 views

### Complexity of OBDD isomorphism (representing same function after permutation of variables)?

According to wikipedia Ordered Binary Decision Diagarams (OBDD) are a data structure that is used to represent a Boolean function.
OBDD is a DAG with two sinks $0,1$.
The size of the BDD is number ...

**2**

votes

**1**answer

157 views

### Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...

**0**

votes

**0**answers

77 views

### Reduction from 3-Partition to a cutting problem

My problem is the following:
Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$.
Output: $n$ sets of 3 numbers
Task: Cut the $b_i$'s into $3n$ integers ...

**3**

votes

**0**answers

163 views

### Derandomization barriers in complexity theory applicable as barriers to constructive arguments replacing probabilistic method

The probabilistic method as first pioneered by Erdős (although others used this before) shows existence of a certain object while finding that object may take exponential time.
(1) Is there any ...

**3**

votes

**1**answer

565 views

### Claimed Quadrature Results seem Impossible

We've been preparing a preprint that shows that the convergence bounds proved for tanh-sinh quadrature for numerical integration, cannot possibly hold, and an error must exist - since they imply a P ...

**5**

votes

**1**answer

270 views

### Division by $n$ in elliptic curves

Let $E/\mathbb F_{p^m}$ be an arbitrary elliptic curve over the Galois field $\mathbb F_{p^m}$, and let $$[n]^{-1}(P)\cap E(\mathbb F_{p^m})=\{Q\in E(\mathbb F_{p^m})\mid nQ=P\}.$$ Also let ...

**11**

votes

**3**answers

369 views

### Algorithmic complexity of formal proof verification?

In this question, suppose $S$ is some popular real-world automated proof system that is stronger than or equivalent to Peano Arithmetic. I would be happy with a positive answer to the following for ...

**2**

votes

**1**answer

50 views

### Complexity of recognizing equivalent translation surfaces

"A translation surface is a union of polygons with pairs of parallel edges identified by translation, up to cut and paste equivalence."
I take that succinct (and not fully precise) definition ...

**4**

votes

**1**answer

79 views

### Complexity of this minimization

For integer $N$ consider the mapping $$f : (0,1)^N \to \mathbb{R}, \quad x \mapsto \min_{b \in \{0,1\}^N} \left\{ x^b + x^{1-b} \right\},$$
where $x^b = x_1^{b_1} \cdots x_N^{b_N}$ and $1-b = (1-b_1, ...

**4**

votes

**1**answer

199 views

### Complexity of linear solvers vs matrix inversion

Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...

**1**

vote

**1**answer

168 views

### On Knot Equivalence problem statement

How is the knot equivalence problem represented?
By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with ...

**16**

votes

**1**answer

1k views

### Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...

**1**

vote

**0**answers

40 views

### Complexity of $\mathsf{gcd}(a,b)\bmod N$

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$.
My query is given $N,a,b$ where $a,b$ is $n$-bits ...

**1**

vote

**0**answers

46 views

### Complexity theory and closed form formulas in analysis

My question concerns definitions of "closed form" solutions. In hamiltonian systems this is closely related to complete integrability. In this context closed form can refers to having $(q(t),p(t))$ ...

**2**

votes

**2**answers

256 views

### Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...

**48**

votes

**3**answers

3k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this ...

**2**

votes

**1**answer

205 views

### Effectively non-recursiveness of some sets

A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$. A set is effectively non-recursive if it is r.e. and its ...

**1**

vote

**1**answer

148 views

### What is the fastest way to sort numbers lexicographically?

I have $N$ sequences of numbers. None of them is longer than $10^6$. I want to sort those sequences lexicographically. For example, given sequences {1, 2, 4}, {1, 2, 3}, {2, 5, 7}, {2}, I want to have ...

**2**

votes

**0**answers

73 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{ ...

**1**

vote

**0**answers

73 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?

**1**

vote

**0**answers

21 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 ...

**3**

votes

**1**answer

96 views

### Computational complexity of low rank SDP

Suppose we are given a general SDP of the form with an additinal rank requirement
\begin{array}{rl} {\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\ \text{subject ...

**4**

votes

**0**answers

186 views

### Weighted Median Filtering

Let's begin with a little review of unweighted median filtering.
Suppose I have a list of $N$ real-valued numbers, $x=x_1,...,x_N$. Let $m_i$ be the median of $K$ consecutive values: $m_i=$ ...

**13**

votes

**0**answers

135 views

### Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...

**3**

votes

**1**answer

122 views

### Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...

**2**

votes

**0**answers

194 views

### Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...

**1**

vote

**2**answers

56 views

### Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...

**5**

votes

**0**answers

128 views

### Is there a decomposition strengthening of the Sauer-Shelah Lemma?

Let $S \subset \{-1,1\}^n$. For a subset $A \subset [n]$ let $P_A$ denote the coordinate projection operator on S; in other words let $P_A(S)$ be the coordinate projection of $S$ onto the coordinates ...

**5**

votes

**2**answers

205 views

### How can I prove that these two graph coloring problems are polynomial time equivalent?

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$.
...

**3**

votes

**1**answer

110 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**2**

votes

**0**answers

118 views

### How hard is recognizing a permutation that is a square for the shift product?

This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation ...

**2**

votes

**0**answers

89 views

### Worst case performance of a simple averaging algorithm

Let $u_1,\ldots,u_n$ be a sequence of rationals with finite binary expansion.
Consider the following simple averaging algorithm:
while the sequence is not monotone increasing, pick $i$ with ...

**7**

votes

**1**answer

139 views

### Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Is there a polynomial analog of this problem ...

**3**

votes

**0**answers

52 views

### Existence of universal witness set and efficient sampling of coNP sets

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that ...

**3**

votes

**1**answer

115 views

### Complexity of a very simple graph partitioning problem

The following problem seems like a very simple and natural one, but I am not familiar with any existing work on it; in particular I am hoping to prove it is NP hard:
Let $G$ be a complete weighted ...

**4**

votes

**1**answer

83 views

### testing singularity of integer matrices

I am looking for the best upper bounds on the bit complexity for testing the singularity of an integer $n\times n$ matrix, where each integer is represented with $k$ bits.
I know the fast method for ...

**7**

votes

**1**answer

168 views

### “Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...

**3**

votes

**0**answers

227 views

### A factorial related statement

Is the following promise problem in $\mathsf{NP}$ or $\mathsf{coNP}$ or even in $\mathsf{PH}$?
$$\Pi:\mathsf{Given}\mbox{ }p,a,s\in\Bbb N,\mbox{ }\mathsf{with}\mbox{ }p\mbox{ }\mathsf{a}\mbox{ ...

**0**

votes

**0**answers

210 views

### Probability two random intervals overlap

I'm working on an algorithm for orthogonal line intersection detection and am trying to analyze some things about it. For simplicity, we can consider the problem as follows:
Given N randomly ...

**3**

votes

**1**answer

102 views

### Understanding Corollary 3, Sec. 5.6, of Papadimitriou's Computational Complexity

I am struggling to understand Corollary 3 from Section 5.6 of Papadimitriou's Complexity Theory book (Addison-Wesley, 1993). It got me completely confused... If anyone out there has read it and ...

**8**

votes

**1**answer

175 views

### Most computationally efficient Littlewood-Richardson rule

There are many, many different versions of the Littlewood-Richardson rule: the original characterization via Yamanouchi words, Remmel's version, a description via the Poirier-Reutenauer bialgebra, the ...