For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

learn more… | top users | synonyms

6
votes
1answer
323 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 ...
2
votes
0answers
106 views

How to argue about state transitions?

Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...
2
votes
1answer
476 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
1
vote
2answers
457 views

Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?

Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable problem. So, is there constructive proof?
8
votes
2answers
315 views

Reduction rules for inductive types

(I'm not sure if I should post this here rather than at Theoretical Computer Science, I've found a lot of type theory related questions on MathOverflow) I'm working in Martin-Löf type theory with ...
0
votes
1answer
151 views

Subset-Free Codes

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum ...
6
votes
2answers
1k views

Is there any math foundation for map/reduce?

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication. First, this is not exactly how monoids work, and second, this ...
4
votes
2answers
205 views

What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title. Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary ...
7
votes
2answers
867 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 ...
12
votes
1answer
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 ...
3
votes
1answer
678 views

Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge? For example, consider $K_4$ with vertices ...
2
votes
1answer
192 views

Recoving an unknown tree graph with knowledge of root node to leaf node distances

Imagine I have an unknown (undirected) tree graph, $G$, with some unknown number of nodes $||V||$. However, I know the edge-length between nodes is of fixed size, $L_{edge} = 1$, and I have access to ...
4
votes
1answer
239 views

Inverse of Kleisli star, or “extension operator”

While thinking about monads in the theory of denotational semantics, I have made an observation about the Kleisli category that I would like to check Suppose $F : \mathcal D \to \mathcal C$, $G : ...
3
votes
1answer
278 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 ...
2
votes
2answers
471 views

Threading pinholes in the wall of cylinder to pass through an internal coordinate

Imagine I take a sheet of paper and use a pin to generate an $N$x$M$ rectangular array of small holes. I then fold the sheet to form a cylinder of radius $r_c$ and height $h_c$, where there are $N$ ...
1
vote
1answer
223 views

Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without “being able to know” one of the discrete logs involved (formal definition given in question)?

Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
1
vote
0answers
129 views

Optimizing for a unique outcome of a probabilistic marriage problem

Let's say I have some number of individuals who are single, $(b_1, ..., b_N) \in B$, and for every possible pairing of two individuals, $b_i$ and $b_j$, I happen to know the exact probability that the ...
0
votes
1answer
171 views

Is there a name for a formula to calculate ascending numbers to a quadratic-like sequence?

For e.g. any range of number 0 - n 0 1 2 3 4 5 6 to: 0 2 4 6 4 2 0 Is there a name for this kind of formula or calculation?
4
votes
3answers
685 views

Estimating the fractal dimension of a point cloud

I have finite set of geolocation point data, and I'd like to estimate the fractal dimension. I know there are several ways to do this, and some of them give different numbers. What is the most ...
2
votes
1answer
314 views

Complexity of computing derivatives

Sorry if this is too simple. This is my first question here. Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point ...
3
votes
1answer
237 views

Numerical Beta Function

Anyone know a fast and concise way of calculating the Beta $B(a,b)$ function for smallish (<10) real $a$ and $b$. For integer $a$ and $b$ I have: $B(a,b) = \prod\limits_{j=1}^b \frac{j}{a+j}$ ...
7
votes
1answer
296 views

RAM simulating another RAM

(Cross-posted from cstheory-stackexchange) The following fact seems to be used implicitly in cs theory, particularly algorithms. Given a RAM machine $M$ running in time $O(f(n))$, another RAM machine ...
0
votes
1answer
519 views

Transition Graph per alphabet?

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
2
votes
1answer
1k views

How many cpus needed to check a 100 million digit prime number efficiently? [closed]

If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
1
vote
3answers
358 views

Operator probability in a RPN string

Consider the set $S_n$ of all strings of length $n$ ($n$ integer, $n \geq 3$) representing an expression in RPN ( http://en.wikipedia.org/wiki/Reverse_Polish_notation. ) Assumptions (to simplify): ...
1
vote
2answers
487 views

Hash functions and inner product

Hi all, As a part of a research I'm working on (involving derandomization of linear threshold functions), I'm trying to understand the following problem: Is there a small (polynomial rather than ...
1
vote
1answer
406 views

Decomposing a sphere (or defomed sphere) into a vertex-transitive graph with fixed-length curved edges

Please see the original problem specification (which Joseph O'Rourke was responding to in his answer) below. Motivation - I'm interested in a particular case of the problem where one wants to ...
1
vote
0answers
207 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
1
vote
1answer
258 views

Constructing a graph that approximates a sphere using rotationally symmetric building blocks with equal numbers of edges

I'd like to construct a graph that approximates a sphere in 3-space, but I'm placed under the following constraints: (1) - I am only allowed to use a construction block, $v_i$, consisting of a single ...
6
votes
6answers
3k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
1
vote
1answer
129 views

Inferring geometric properties of a polytope from intersection volumes of spheres at unknown coordinates on its surface

Let's say we have some polytope $P$ in 3-space (which is not necessarily convex) as well as some number of points on its surface, $(g_1, ..., g_N)$. We are provided no information about the ...
1
vote
0answers
343 views

NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
8
votes
1answer
448 views

Magma “actions” (or alternatively, “What is the Yoneda lemma for magmas?”)

Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all ...
4
votes
1answer
340 views

Growth zeta-functions of regular languages

Dear All, my following question may be known and ought to be known, so in case it is folklore please could you give me the references. To start, it is obvious that growth of rational languages are ...
7
votes
1answer
547 views

The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input. Are ...
2
votes
1answer
280 views

Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
2
votes
1answer
430 views

Lipschitz constant of Laplace-Beltrami Operator

I already asked this question at stackexchange with no response - so I'll try here. I'm reading a paper on discrete differential geometry: Meyer et.al. They define the Laplace-Beltrami operator at ...
2
votes
2answers
229 views

Correcting bias in samples selected by a prediction

Here is the scenario: I'm trying to find as many golden tickets as I can, so that I can sell them to kids that want to go on a tour of Wonka's chocolate factory. Fortunately, I have a machine that ...
2
votes
1answer
685 views

Official name and complexity of k-way balanced set partitioning? What is the best heuristic?

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices ...
2
votes
3answers
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
2answers
485 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
1answer
157 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
5answers
578 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
0answers
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
3answers
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
0answers
88 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
0answers
229 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
2answers
563 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
1answer
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
1answer
550 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 ...