All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

11
votes
0answers
378 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
11
votes
0answers
193 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
7
votes
0answers
185 views

How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
7
votes
0answers
233 views

Homomorphic Compression

Can there be an algorithm such that, given plaintext data P,Q, and compression function e, Such that if we treat P and Q as a number (a series of bits): $$\begin{eqnarray*}e(P + Q)& =& e(P) ...
7
votes
0answers
164 views

Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?

Remark: I recently rewrote this post, hoping to get answers! I am analyzing the following experiment: Pick an $x \in \{0,\ldots,2k\}$ uniformly at random Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
6
votes
0answers
73 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
5
votes
0answers
57 views

Where can I learn more about the “else” operation / “else monoid”?

(The set of natural numbers $\mathbb{N}$ starts at $0$ for me.) Let $X$ denote a set, and define $X_\bot = X \uplus \{\bot\}.$ Let $\mathbf{else}$ denote the binary operation on $X_\bot$ defined as ...
5
votes
0answers
61 views

Elementary proof of compact space = exhaustible space?

(This is a repost of a question I asked last year on cs.stackexchange.) The work of Martín Escardó has demonstrated close parallels between classical topology on one hand and computability on the ...
5
votes
0answers
166 views

How to list the prime factorised natural numbers?

Today I set out to invent a two character numeral system designed to make factorization trivial. Indeed, it lets one factor non-trivial numbers with over thousand digits within 30 seconds per hand - ...
5
votes
0answers
109 views

Are points on the complex plane sufficient to solve every solvable equation composed of the hyperoperators, their inverses, and complex numbers?

Some background: I'm programming a maths environment. I'm computer science, so please excuse any probable ignorance and lack of precision in my question. It seems $i$ and complex numbers were ...
4
votes
0answers
109 views

A problem on 0-1 matrices.

Given a 0-1 matrix $A$, is there an efficient way to find all 0-1 vectors $x$ such that $Ax = v$ where the entries of $v$ belong to a set $\{a,b\} \subseteq \mathbb{Z}$ of size $2$? Note that $v$ is ...
4
votes
0answers
83 views

This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
4
votes
0answers
131 views

Computational hard math problem

Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& ...
4
votes
0answers
514 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
4
votes
0answers
407 views

algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
4
votes
0answers
133 views

Hardness of perimeter minimization?

Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant. What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum? Providing references is highly ...
3
votes
0answers
23 views

What does “the activation of a basis” mean?

In the paper Rajat Raina, Alexis Battle, Honglak Lee, Benjamin Packer, Andrew Y. Ng, Self-taught learning: transfer learning from unlabeled data, ICML '07 Proceedings of the 24th international ...
3
votes
0answers
51 views

Examples of calculus on “strange” spaces

I am interested in examples of calculus on "strange" spaces. For example, you can take the derivative of a regular expression[1][2]. Also the concept extends past regular languages, to more general ...
3
votes
0answers
19 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
3
votes
0answers
53 views

Complexity of finding set of sets with maximum cardinality and constrained coverage.

Given a set of sets $S = \{S_1, S_2, \dots, S_n$}, let $S^{'} \subset S$ be the largest subset of S that obeys $\left| \bigcup_{S_i \in S^{'}}{S_i} \right| \leq k$. What is the complexity of finding ...
3
votes
0answers
51 views

Why is this not a poset after adding zero?

The problem    Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
3
votes
0answers
165 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
3
votes
0answers
131 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, ...
3
votes
0answers
84 views

A Tricky Quetiones on Creative Algorithm in Graph

an agent is works between n producer and m consumers. i'th producer, generate $s_i$ candy and j'th consumer, consumes $b_j$ candy, in this year. for each candy that sales, agent get 1 dollar payoff. ...
3
votes
0answers
72 views

Computability and continuous real functions

I have found somewhere the following statement: "Every computable real function has to be continuous," but I'm not able to prove it and the "proofs" that I found in some blog posts don't seem ...
3
votes
0answers
69 views

What is the desirable function identification when setting up arrows in the category of types?

My question is which functions can not be allowed in a statically typed programming language, so that the "canonical" category is less coarse than what you get if you define it's arrows to be ...
3
votes
0answers
110 views

Related paradigms in Computer Science and Mathematics

I've read in a number of places discussions on whether Mathematics is a branch of Computer Science and vice-versa (see here for example) Having a background in both, I know that the Computer Sciences ...
3
votes
0answers
84 views

Minimizing set intersection/block design

I asked this question on the CS theory stack exchange, but didn't get an answer. Was wondering whether anyone here might have some insight. Thanks in advance for any help. Given 3 parameters $s, r$ ...
3
votes
0answers
92 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
3
votes
0answers
86 views

Boltzmann machines - motivation for the energy function

I've been studying Boltzmann machines lately and was wondering if anyone could give me a "high-level" explanation or motivation for the energy function used: $$E = -\sum_{i<j} w_{ij} \, s_i \, s_j ...
3
votes
0answers
175 views

Binomial Coefficients optimization

Given n and R, I have to find the minimum value of k such that: $${(2^n)-1 \choose k}\bmod(2^n)==R$$ Where $k = \{0, 1, 2, \dots, 2^n-1\}$ Here ${n \choose k}$ is the binomial coefficient ...
3
votes
0answers
51 views

Covering $n$ points with fewest disks with fixed radius $\epsilon$

The title says it all. I have a set of $n$ points in $\mathbb{R^{2}}$ and I am looking for an algorithm that tells me the fewest numbers of disks of radius $\epsilon$ that cover the set of $n$ ...
3
votes
0answers
202 views

Amortized Analysis for (2,5)-Tree

I need some help with the following problem Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 ...
3
votes
0answers
334 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
2
votes
0answers
26 views

Decidability - Complexity

Can someone tell me where I can get some information about the following? We have linear differential equations with polynomial coefficients depending on x. $a_n(x)y^{(n)}+ \dots ...
2
votes
0answers
27 views

Stuck in a Context-Free Proof

I am trying to work through the pumping lemma for CFLs. $L_1 = \{0^n 1^{mn} : n,m \in \Bbb N\}$ I am trying to find a contradiction. I have currently chosen $z= 0^p1^{2p}$ to be my string. Then ...
2
votes
0answers
40 views

Neighbor-full partition of $\{0,1\}^n$

What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$) We say $A$ and $B$ are neighbors if their ...
2
votes
0answers
36 views

What exactly is wrong with this argument (Lucas-Penrose fallacy)

Argument "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
2
votes
0answers
81 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
0answers
14 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
2
votes
0answers
21 views

Optimality of lower bounds for Max-cut on specific graphs

The Max-Cut problem asks to find a subset $S$ of the vertices of a graph (with $m$ edges) such that the number of edges from $S$ to it's complement is as large as possible. The size $|M|$ of a max cut ...
2
votes
0answers
65 views

Trouble with induction on the length of a word

In the accepted solution of the question If L is regular, prove that $\sqrt{L}=\{w:ww\in L\}$ is regular the answerer made the claim that "What's left is to show that $δ ′ (q_{0}' ,w)=h$ , which can ...
2
votes
0answers
46 views

Hashing Probability

I have just started to learn about the topic of hashing. I understand how it works and the difference between closed address and open address, but do not know how to calculate the probability of a ...
2
votes
0answers
20 views

Compute the coefficients of a Runge-Kutta method

Let $f$ be a Lipschitz continuous function, $(a_{ij})_{1\le i,j\le s}$ and $(b_i)_{1\le i \le s}$ some real numbers, $x_0 \in \mathbb{R}$ and $h$ an arbitrary small positive number. Under some ...
2
votes
0answers
70 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
2
votes
0answers
51 views

(Concrete) mathematical aspects of programming

It is often said that progamming is mathematics as it "makes use" of "discrete mathematics". However, I would like to ask a more concrete question: what are the concepts of a programming ...
2
votes
0answers
36 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
2
votes
0answers
65 views

What computations would advance math knowledge a lot?

Suppose we where given a super computer that would be capable of computing anything, but only for one day. We could for instance compute many of the Ramsey numbers. What would be some computations ...
2
votes
0answers
44 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...