**-4**

votes

**0**answers

31 views

### Hamiltonian systems plus epsilon [on hold]

EDIT: A $2n$-dimensional hamiltonian system is completely integrable if it has $n$ linearly independent (over $\mathbb R$) conserved observables ($C^\infty$ functions on phase space, among which is ...

**0**

votes

**0**answers

49 views

### Polynomial time approximation schemes

The relationship between the minimum vertex cover and maximum independent set is a well established one. I was wondering if
If for some class of graphs $\mathcal{S}$ there exists a PTAS or even an ...

**2**

votes

**1**answer

572 views

### What is the time complexity of approximated SVD

Full SVD, on an m*n matrix $A$, $[U,S,V] = svd(A)$, would cost $O(m^2n + mn^2 + n^3)$ time.
But what is the time complexity if we only need the $k$ largest singular values, say, $[U_k,S_k,V_k] = ...

**33**

votes

**2**answers

2k 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 ...

**10**

votes

**2**answers

2k views

### Best-case Running-time to solve an NP-Complete problem

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...

**1**

vote

**2**answers

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

**2**

votes

**1**answer

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

**14**

votes

**1**answer

970 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**8**

votes

**2**answers

1k views

### How many Complexity Classes do you know?

We can read about the main complexity classes in textbooks and online in Wikipedia:
http://en.wikipedia.org/wiki/Computational_complexity_theory
However, in papers, there are a lot of important new ...

**1**

vote

**1**answer

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

**11**

votes

**2**answers

674 views

### Fold-and-cut problem in three dimensions

The fold-and-cut theory states that "Any shape with straight sides can be cut from a single (idealized) sheet of paper by folding it flat and making a single straight complete cut. Such shapes include ...

**2**

votes

**0**answers

62 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

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

**30**

votes

**4**answers

2k views

### Why is “P vs. NP” necessarily relevant?

I want to start out by giving two examples:
1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...

**1**

vote

**0**answers

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

**13**

votes

**0**answers

124 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

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

**3**

votes

**0**answers

70 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=$ ...

**5**

votes

**2**answers

190 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$.
...

**4**

votes

**1**answer

411 views

### The relationship between P vs NP problem and “Kolmogorov complexity with time”

Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$.
Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?"
Is it Problem1 $\in ...

**3**

votes

**0**answers

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

**7**

votes

**1**answer

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

**1**

vote

**0**answers

102 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}$, ...

**1**

vote

**1**answer

52 views

### Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$,
$$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...

**1**

vote

**0**answers

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

**0**

votes

**0**answers

58 views

### Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
...

**3**

votes

**1**answer

109 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

188 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

**0**answers

25 views

### Relation between indexed languages (OI-macro or context-free tree) and scattered context languages

I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...

**0**

votes

**0**answers

26 views

### Complexity of edge coloring graphs of sufficiently large maximum degree

I am interested in the complexity of edge coloring
graphs with $\Delta(G) > |V(G)|/3$.
This is closely related to the Overfull conjecture (OC).
Conjecture/Question: If a simple graph G with n ...

**5**

votes

**0**answers

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

**7**

votes

**1**answer

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

**2**

votes

**0**answers

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

**3**

votes

**1**answer

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

**11**

votes

**2**answers

339 views

### Can Schwartz-Zippel be formulated for commutative rings instead of fields?

The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

29 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 string to an element in $A$ such that ...

**3**

votes

**1**answer

113 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

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

**13**

votes

**3**answers

913 views

### Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...

**8**

votes

**1**answer

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

**15**

votes

**2**answers

914 views

### Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns ...

**4**

votes

**3**answers

259 views

### Complexity of a problem remotely related to the discrete logarithm $A=x g^x$

Let $x,g \in \mathbb{F}_p^\ast$.
Given $g$ and either
$$ A = x g^ x$$
or
$$ A = x g^{x^2-1}$$
find $x$.
What is the complexity of solving this?
Is there a reduction to the discrete ...

**6**

votes

**1**answer

166 views

### Computation Time of Smith Normal Form in Maple

I am using maple to compute the Smith Normal Form of a matrix of size 120*120 and it seems that I will never get an answer back. I have checked my code for small cases and I believe that it is ...

**0**

votes

**0**answers

146 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

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

**2**

votes

**1**answer

112 views

### Connection between Barnette conjecture and hardness of cubic graph decomposition

Motivated by this post on cubic graphs decompositions and the connection to Barnette's conjecture, I am interested in decomposing a connected bridgeless cubic graph into edge-disjoint paths of length ...

**11**

votes

**1**answer

826 views

### Evidence that Graph Isomorphism problem is not $NP$-complete

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...

**18**

votes

**0**answers

530 views

### Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...

**3**

votes

**0**answers

104 views

### Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...