# Tagged Questions

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

599 views

181 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)$ ...
334 views

523 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 F$...
139 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 ...
51 views

### Hyperplane Problem

Given $M$ points in $\mathbb{R}^{N}$, (where $M$ is larger than $N$) I was wondering if there is an approximation algorithm to find a hyperplane which goes through the origin and also intersects as ...
89 views

### Reverse Automorphic Numbers

I recently stumbled across Automorphic Numbers (definition and examples). In simple words, a number $n$ is said to be automorphic if last $d(n)$ digits of $n^2$ are $n$ itself (where $d(n)$ is ...
63 views

### Is there a better representation than p-adics for exact computer arithmetic?

I stumbled across Quote notation and went hog wild. But when I stumbled on a technical detail I received a very discouraging comment: I think those authors may have been a bit short-sighted, ...
195 views

### Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
41 views

### Finding if f(n) = O(g(n) and vice versa…

Define $f(n) = \{ 3n-1$ if n is divisible by 3.. $n^2$ otherwise and $g(n) = \{ n^2$ if n is divisble by 3.. $2n$ otherwise Is $f(n) = O(g(n))$, is $g(n) = O(f(n))$? Here is my attempt at solving ...
28 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 ...
38 views

120 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. ...
100 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 ...
90 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 ...
143 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 ...
107 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$ ...
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 ...