The computer-science tag has no wiki summary.

**0**

votes

**1**answer

441 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

**1**answer

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

**3**answers

331 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

**2**answers

443 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

**1**answer

393 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

**0**answers

201 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

**1**answer

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

**5**

votes

**6**answers

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

**1**answer

125 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

**0**answers

335 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

**1**answer

411 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

**1**answer

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

**6**

votes

**1**answer

497 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

**1**answer

257 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

**1**answer

412 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

**2**answers

226 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

**1**answer

585 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

**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

435 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

151 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

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

**9**

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

80 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

212 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

470 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

177 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

528 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

550 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

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

**1**

vote

**0**answers

725 views

### Lambert's Cosine Law - Simple algebraic rearrangement problem [closed]

Let $I(x,y)$ be the intensity at position $(x,y)$, $\rho(x,y)$ be the albedo at this point (a constant), $n=(p,q,1)$ be the surface gradient vector and $s_{0},s_{1},s_{2}$ all be vectors from the ...

**8**

votes

**1**answer

1k 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

338 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

321 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

452 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

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

**1**

vote

**0**answers

336 views

### Catmull-Clark Subdivision and weights

I've been toying with a Catmull-Clark subdivision algorithm; I also compared my results to results I found online (e.g. images.google.com).
The weights used to relocate the old vertices of the mesh ...

**4**

votes

**1**answer

239 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

210 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

257 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

661 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

408 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

248 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

413 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

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

**26**

votes

**17**answers

6k 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

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

**6**

votes

**1**answer

365 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

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