**2**

votes

**3**answers

2k views

### Worst known algorithm in terms of Big-O (more precisely Big-theta)?

Hello,
I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...

**3**

votes

**2**answers

501 views

### Partition a square into sub-rectangles with restrictions

Is there an algorithm to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions:
1- No vertical line crosses any ...

**0**

votes

**1**answer

158 views

### the maximal length of a special dicksonian sequence

First, we define a sequence $t_{1},t_{2},\cdots,t_{k}$ of n-tuples dicksonian, if $\forall 1\leq i < j\leq k,$ there does not exist a non-negative n-tuple t such that
$t_{i}+t=t_{j}.$ For example, ...

**3**

votes

**5**answers

579 views

### Is the following two-dimensional graph likely to be globally rigid?

Consider the two-dimensional non-planar graph $G$, with known topology and edge lengths $(r_1, r_2, ... r_N) \in R$, but unknown vertex coordinates. We further specify that:
All vertices within a ...

**8**

votes

**0**answers

1k views

### Question on randomness extractors

Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...

**26**

votes

**3**answers

2k views

### “Simpler” statements equivalent to Con(PA) or Con(ZFC)?

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...

**0**

votes

**0**answers

92 views

### Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?

I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...

**2**

votes

**0**answers

235 views

### what is the largest gap between rank and approximate rank

$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...

**1**

vote

**2**answers

603 views

### best deterministic complexity for factoring polynomials over finite field

I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...

**2**

votes

**1**answer

187 views

### Parsing of Stochastic Contex-Free Grammars (SCFGs)

I am interested in parsing of general SCFGs.
I am aware of the Earley parser for the general CFGs. The only general algorithm for parsing SCFGs that I am aware of is the Earley-Stolcke parser : ...

**1**

vote

**1**answer

558 views

### final step(s) for a proof that a function is not primitive recursive

My function is $f:\mathbb{N} \rightarrow \mathbb{N},\ f(n)=2\uparrow ^n 3$ , the Ackermann(-Péter) function, with the second argument fixed to 3 (and "$\uparrow$" the Knuth up-arrow), which I believe ...

**15**

votes

**2**answers

616 views

### Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:
Find a decision procedure for determining if an arbitrary semilinear set
is ...

**4**

votes

**2**answers

315 views

### Approximate search space on a 5x5x5 cube with 3 different possible classes?

Hey all,
I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...

**9**

votes

**1**answer

2k views

### All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it.
Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...

**4**

votes

**1**answer

357 views

### Injections to binary sequences that preserve order

Suppose we have a countable set S with a total order. Can we give an injection from S to the set of finite binary sequences that end in all zeros that preserves the ordering? The order on binary ...

**3**

votes

**2**answers

339 views

### Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).

Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo ...

**5**

votes

**2**answers

477 views

### A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size

I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a ...

**5**

votes

**3**answers

525 views

### Appropiate models of numerical computation

Hello,
in contrast to the more discrete part of computational mathematics (cryptography, combinatorial computation), numerical mathematics seems to ignore typical questions of theoretical computer ...

**4**

votes

**1**answer

246 views

### Turing Machine which generates order on the set of its states

This question is related to this one Do Turing Machines generates any nontrivial lattice on the set o symbols or states?
The Turing machine (TM) is an abstract model for effective implementation of ...

**1**

vote

**1**answer

215 views

### Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

Second question, probably better: Turing Machine which generates order on the set of its states
I would like to ask ( if it is not terribly obviously wrong):
Do Turing Machine generates ...

**1**

vote

**2**answers

289 views

### Positive & Negative Arity

Hi,
You can talk about the arity of a function or an operation - something like addition could have an arity of 2, and negation usually has an arity of 1.
A paper I am reading is talking about ...

**2**

votes

**2**answers

724 views

### viewing the second fundamental form as a tensor

Dear all,
Thank you for your time reading this post. I am a student in computer science so this viewpoint of the second fundamental form may be interesting to you.
I would like to understand the ...

**3**

votes

**2**answers

1k views

### finding numbers at k hamming distance

Guys,
I have N < 2^n randomly generated n-bit numbers stored in a file the lookup for which is expensive. Given a number Y, I have to search for a number in the file that is at most k hamming ...

**8**

votes

**5**answers

425 views

### Syntactically capturing complexity classes

Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...

**1**

vote

**1**answer

255 views

### Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}?
One case this is possible is when ...

**4**

votes

**1**answer

519 views

### What fails when using call/cc as realizer of the Peirce formula

Define the axiom constants $p_{A,B}^{((A\rightarrow B)\rightarrow A)\rightarrow A}$ as realizers of the Peirce formula, and $f_A^{\bot\rightarrow A}$ as realizers of the Ex Falso Quodlibet. Then ...

**0**

votes

**0**answers

389 views

### Applications of the property of Kendall-Mann numbers

I am looking for an application of the Kendall-Mann sequence (KM) which uses the property $M(n+1)/M(n) = n - 1/2 + O(1/n)$ ($n \to \infty$) in science ( computer science ( sorting), physics, biology ...

**28**

votes

**17**answers

7k views

### Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scienctists post questions looking to learn things ...

**1**

vote

**2**answers

762 views

### Verifying a sequence that converges to pi [closed]

A computer program ouputs the digits of $\pi$ by evaluating the recurrence relation
$a_{n+1} = a_n + sin \ a_n$
with $a_0 = \frac{6}{5}$
Does the sequence actually converge or is this just ...

**5**

votes

**1**answer

412 views

### What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

This question is now also on http://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...

**4**

votes

**2**answers

635 views

### Coloring edges on a graph s.t. the set of edges for any two vertices have no more than 'k' colors in common

Please imagine the case where one has a planar graph, $G$, with a set of $|V|$ vertices, $(v_1, ..., v_{|V|}) \in V$, and $|E|$ edges, $(e_1, ..., e_{|E|}) \in E$. Now, provided a total of $N$ ...

**8**

votes

**3**answers

2k views

### n-dimensional voronoi diagram

Hi, I need to compute the voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind ...

**5**

votes

**1**answer

366 views

### Are innermost reductions perpetual in untyped $\lambda$-calculus?

Background
In the untyped lambda calculus, a term may contain many redexes, and
different choices about which one to reduce may produce wildly
different results (e.g. $(\lambda x.y)((\lambda ...

**2**

votes

**3**answers

320 views

### Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...

**15**

votes

**7**answers

1k views

### Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough
to express all functions, Ackermann function being probably the best
known example.
Now, in the logic courses (that I have had look ...

**5**

votes

**1**answer

335 views

### Drawing graphs on circles

Please consider the following problem:
Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices.
Task: place equidistantly the vertices of $G$ on a circle of unit ...

**5**

votes

**1**answer

4k views

### Meaning of \Subset notation

The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...

**29**

votes

**1**answer

3k views

### An edge partitioning problem on cubic graphs

Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...

**6**

votes

**1**answer

449 views

### post correspondence problem variant

Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...

**4**

votes

**3**answers

1k views

### Optimal packing of spheres tangent to a central sphere

Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$.
My question concerns optimal values for the ...

**0**

votes

**3**answers

298 views

### boolean functions and averaging / counting

Hey guys,
I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...

**1**

vote

**2**answers

860 views

### What is the right citation for the power iteration method to find eigenvalues?

What is the right citation for the power iteration method to find eigenvalues, if I want to cite the method in a paper? I've seen some Google PageRank references in this context. But Brin and Page ...

**2**

votes

**4**answers

798 views

### Enumerative algorithm through inclusion-exclusion

Hello everybody !
I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...

**3**

votes

**1**answer

478 views

### Approximating an integral representation of the Number Partition Problem

One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or ...

**2**

votes

**0**answers

262 views

### Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...

**3**

votes

**1**answer

205 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...

**8**

votes

**1**answer

917 views

### Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice

Please imagine a discrete random walk on an N-dimensional rectangular lattice with dimensional lengths $(l_1, ..., l_N) \in L$ and total lattice points $P = \prod{l_i}$, for $i = 1, ..., N$. At each ...

**1**

vote

**2**answers

1k views

### post correspondence problem

I have read a couple of proofs for the undecidability of the post correspondence problem, but neither reference gave a concrete example of two lists of words over a fixed alphabet such that the ...

**1**

vote

**2**answers

859 views

### Practical use of probability amplification for randomized algorithms

Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon < 1/2$. We know that we can replace the error term for any inverse polynomial. And the inverse polynomial ...

**2**

votes

**1**answer

291 views

### Approximating a recursively-defined function

Let $$f(k) := \frac{2k-1}{k}\bigl(1-\sum\limits_{i\lt k}\frac{i\ f(i)}{k+i-1}\bigr)$$ for $k\in\mathbb{N}^{+}$.
So $f(1) = 1$, $f(2) = 3/4$, $f(3) = 35/72$, etc.
(This function arises when ...