# Tagged Questions

**3**

votes

**1**answer

194 views

### counting patterns in a word

Do algorithms exist to find all the patterns in a word?
I would like to count all the 3-step increasing sequences (123 i.e. 123, 234 & 345) in some word in the alphabet {1,2,3,4,5}
such as ...

**6**

votes

**1**answer

313 views

### compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...

**1**

vote

**0**answers

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

**3**

votes

**1**answer

160 views

### bounding the probability that a polynomial is near 0

Given a polynomial $p(x_1,\ldots, x_k)$ in $k$ variables with maximum degree $n$, and $x_1,\ldots, x_k \in [0,1]$. Suppose $\max_{x \in [0,1]^k} p(x) = 1$, can we get an upper bound on the probability ...

**4**

votes

**1**answer

412 views

### Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418

I am not familiar with newforms, so this may not make any sense.
OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3]
Numerical evidence suggest that up to $10^5$
$$ ...

**4**

votes

**1**answer

502 views

### Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?
...

**1**

vote

**0**answers

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

**3**

votes

**0**answers

276 views

### Connected Sum Decomposition of a Knot

Given a composite knot, is it possible to decompose it in prime knots by an algorithm that runs in polynomial time?

**3**

votes

**3**answers

667 views

### Problem regarding subsets that sum to 0

Let $X=\{x_1,...,x_n\}$ be a multiset of $n$ real numbers, and let $x_1+\dots+x_n = 0$. Is there a way to find the maximum number of unique subsets any $X$ can have given $n$, such that each subset ...

**4**

votes

**1**answer

617 views

### Algorithmic war

No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...

**1**

vote

**0**answers

442 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]$)
...

**0**

votes

**2**answers

208 views

### equivalence of NL Definitions

Hi,
How to prove that the two definitions of the complexity class NL are equivalent.
1st definition is with a non deterministic logspace TM, and the second is with a deterministic logspace verifier ...

**7**

votes

**2**answers

329 views

### Ordinals and complexity classes

What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...

**7**

votes

**2**answers

833 views

### Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...

**5**

votes

**2**answers

402 views

### Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem.
Inputs:
A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with ...

**2**

votes

**2**answers

622 views

### Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph

Hi everyone!
This is my first post, apologies if I made any mistakes anywhere.
Here goes the question:
Consider all length 7 binary sequences.
Let $X$ be the set of sequences with hamming weight 3 ...

**1**

vote

**1**answer

269 views

### A regular n,2d graph is a good expander.

Context
Reading about Expanders
Setup
A regular n,2d graph is generated as follows:
generate d random permutations of [n]
connect the edges; giving a n,2d regular graph
...

**5**

votes

**1**answer

994 views

### Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value

Setup
Let $A$ be a stochastic matrix.
Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$.
Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$
Question:
...

**2**

votes

**1**answer

118 views

### Structure of class P

Hi all,
1. Has there been any work done on trying to distinguish between different Polynomial Time Hierarchies say, O(n) vs O(n^2) problem? May be Turing Machine is too general for that. May be the ...

**6**

votes

**2**answers

375 views

### Complexity of detecting a convex body in $\mathbb{R}^n$?

Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,
$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
The ...

**11**

votes

**6**answers

1k views

### Compressing Graphs (Kolmogorov complexity of graphs)

What is known about compressing graphs? Here, with "compressing", I mean something like "putting a graph into a zip program"; or with a more technical expression, what is know about the Kolmogorov ...

**10**

votes

**1**answer

503 views

### Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...

**12**

votes

**1**answer

2k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...

**1**

vote

**1**answer

219 views

### Pseudorandom Generator vs Constant Depth Circuits / Branching Programs

Hi.
I am looking for a survey on the state of the art in pseudorandom generators vs
(1) constant depth circuits
and/or
(2) Branching Programs
For (1), is "Anindya De, Omid Etesami, Luca Trevisan ...

**1**

vote

**1**answer

485 views

### P vs NP and OWFS

It is known (simple HW exercise) that:
If P = NP, that OWFs (one way functions) can not exist.
It is also known that there is a Universal OWF:
namely, there is a function f:
s.t. if any OWF ...

**2**

votes

**0**answers

166 views

### Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$.
Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled
by their color and a binary string of ...

**4**

votes

**1**answer

712 views

### Finding a vertex of least distance to all other vertices in a graph

Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the ...

**4**

votes

**1**answer

276 views

### Hermit H-machines

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...

**0**

votes

**0**answers

132 views

### Bounds on reducing from NP to SAT

Let M be a non deterministic turing machine.
Suppose M is a TM that runs in T(n) time.
Given an instance of x in {0,1}^n, and the question M(x) accepts?
We can
1) convert M into an oblivious TM ...

**0**

votes

**0**answers

164 views

### Survey on the Power of Non-Uniformity

Non-Uniformity is quite powerful in complexity theory.
For example: BPP is a subset of P/poly.
If NP is a subset of P/poly, then the polynomial hierarchy collapses to Sigma^2.
Question:
Is there a ...

**1**

vote

**3**answers

207 views

### Inequality involving size of nodes & min degree of graph.

Context:
http://www.sciencedirect.com/science/article/pii/S0019995882904776
Lemma 1 on 3rd page.
Question excerpted / rewritten as follows:
(V,E) = a graph on {0,1}^n, where there is an edge ...

**4**

votes

**0**answers

158 views

### Suppose P = BPP; Pseudorandom Generators vs NP Adversary

Suppose P = BPP.
Then we know there exist pseudorandom number generators vs P.
Suppose the adversary is NP.
Now, any pseudorandom number generator that only uses P will fail. (Since NP can invert ...

**2**

votes

**0**answers

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

**4**

votes

**1**answer

650 views

### Turing machines that always halt

Needed for this paper:
Here is a possibly more clear version of my question. A Turing machine (with $1$ tape) has sets of tape letters $Y$, state letters $Q$, two symbols $\alpha$ and $\omega$ that ...

**2**

votes

**1**answer

277 views

### Tail Bound on Binomial

Context: circuit complexity argument:
How do I show that $$\sum_{i=0}^{n/2- \sqrt{n}} {n \choose i} \geq 2^n/50$$ ? (as n goes to infinity)
[This shows up in proving Mod2 is not in ACC(3)].
...

**0**

votes

**0**answers

118 views

### Approximate Solving Linear Equations

EDIT: RESOLVED.
Given:
$$ x, \{r_i\}_{i=1}^m \in \{0,1\}^n$$
$$ \Pr_{i} [b_i = c \cdot x_i] \geq 1/2 + \epsilon $$
We are given:
$$(b_i, r_i)$$
Question:
can we in polynomial time find an ...

**1**

vote

**2**answers

233 views

### Pseudorandom Functions / Pseudorandom Permutations

I'm reading Yao's unpredictability -> pseudorandomness construction
and Goldreich/levin's pseudorandom permutation -> pseudorandom generator construction.
My question is:
is there a direct way to ...

**0**

votes

**2**answers

200 views

### Formal verification in complexity theory

Reading books and papers on complexity theory, I am struck by the extreme degree to which proofs are stated in an intuitive, hand-wavy way. The alternative is to give a lot of details about the coding ...

**3**

votes

**2**answers

319 views

### Has Oracles actually provided intuition for proving anything in Complexity Theory?

[EDIT: I realize this question is soft. I realize some people want to close this question. The goal here is trying to answer the following question:
So I see these research papers that provide papers ...

**1**

vote

**1**answer

304 views

### Open?: Bpp VS EXP^NP

Known:
BPP vs NEXP is open.
BPP is strict subset of EXP^EXP.
Question:
Is BPP vs EXP^NP open?
If so, is there any class between EXP^NP, EXP^EXP concerning which vs BPP it's still open?
Thanks!
...

**9**

votes

**1**answer

557 views

### Polynomial-time complexity and a question and a remark of Serre

My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a ...

**3**

votes

**1**answer

185 views

### Oracle Separation Results: A^O != B^O yet A = B ?

I know that there exists classes $A$ and $B$ such that:
$A^{O_1} = B^{O_1}$, $A^{O_2} != B^{O_2}$.
Now, this is my question: do we know of any classes $A$ and $B$ such that $A=B$, yet
there is an ...

**7**

votes

**3**answers

620 views

### Definition of relativization of complexity class

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?
Usually, these classes and their relativizations seem to be defined in an ad-hoc ...

**1**

vote

**0**answers

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

**2**

votes

**2**answers

231 views

### Oracle Separation Survey

Is there a survey (or a website) somewhere that lists all known separation results?
I.e. it has a list of triples:
$$ (C_1, C_2, A)$$
where
...

**2**

votes

**0**answers

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

**4**

votes

**2**answers

927 views

### the complexity of Lanczos method

Hi, all
I am working on an algorithm which uses Lanczos method to compute K smallest eigenvalue(and their eigenvectos) of a sparse matrix, just want some information or links about the complexity of ...

**2**

votes

**1**answer

179 views

### Survey on Structural Complexity

Alot of the proofs I've been recently reading:
IP / PSpace / MIP / NEXP / randomized reductions
have a certain flavour involving proofs showing equivalence/relation between various complexity ...

**6**

votes

**1**answer

235 views

### Simplices in convex polytopes

This question is a direct generalization of:
Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices
Given a convex ...

**0**

votes

**0**answers

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