**-2**

votes

**0**answers

18 views

### Computer Science/Maths Hamming Distance [on hold]

My professor told us to try and remember the equation used for an upcoming exam, however I'm struggling to fit the equation into the question:
http://i.stack.imgur.com/RoPYG.png
(need a high ...

**-4**

votes

**0**answers

36 views

### simple calculator. [on hold]

i have this gui code on calculator. i don't know how to appear the arithmetic operation on my text field. can some one help me.tnx
import java.awt.;
import java.awt.event.;
import javax.swing.;
...

**4**

votes

**1**answer

165 views

### Constructing the oracle for Grover's algorithm

For a final project in my class, I decided to try to simulate a quantum computer and implement Grover's algorithm. I followed this excellently written blog post by Craig Gidney, and was successful in ...

**5**

votes

**1**answer

95 views

### Algorithm that generates minimum n-simplex that cover n-cube?

Given an $n$-cube with unit volume, is there any algorithm that generates a minimum volume $n$-simplex that covers the $n$-cube?

**11**

votes

**1**answer

433 views

### Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...

**2**

votes

**0**answers

75 views

### Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$.
For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...

**1**

vote

**0**answers

67 views

### Counting models in first order logics without existencial quantifiers

My question is about the posibility of to construct a parameter space of models in a first order theory, finitely presented, with out existencial quantifiers (parameter space in the sense of ...

**11**

votes

**0**answers

301 views

### Does Langton's ant cover every n by 6 gridded torus?

This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus.
For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs ...

**2**

votes

**1**answer

101 views

### cohomology algebra of submanifold in euclidean space

If we write a manifold or CW-complex $X$ as a subset of $\mathbb{R}^n$, in expression of coordinates, for example, \begin{multline}
F(S^2,k+1)=\{(x_1,x_2,x_3,\cdots, ...

**1**

vote

**1**answer

82 views

### Optimal covering

Let consider a problem of optimal covering of Hamming space.
So we have Hamming space $\{0,1\}^n$ and some integer $r$. We want to find a set $A \subseteq \{0,1\}^n$ such that any point from ...

**2**

votes

**0**answers

166 views

### Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning? [closed]

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).
It seems to me that much ...

**3**

votes

**1**answer

468 views

### Mathematics of Computer science and AI [closed]

Computer science and Artificial Intelligence have been fertile grounds for research for decades, not only for Engineers but particularly for Mathematicians. What kinds of Mathematics have emerged ...

**3**

votes

**0**answers

62 views

### Are all $k$th-longest-tour problems equally hard?

It is well known, that determining the shortest and, the longest Hamilton Cycle of a complete graph with real edge weights are algorithmically two sides of the same medal: one transforms to the other ...

**4**

votes

**2**answers

663 views

### How to calculate the sum of remainders of N?

I'm trying to sum the remainders when dividing N by numbers from 1 up to N
$$\sum_{i = 1}^{N} N \bmod i$$
It's easy to write a program to evaluate the sum if N is small in O(N) but what if N is large ...

**5**

votes

**2**answers

323 views

### TM and abstract algebra

Usually, during lectures Turing Machines are firstly introduced from an informal point of view (for example, in this way: http://en.wikipedia.org/wiki/Turing_machine#Informal_description) and then ...

**3**

votes

**1**answer

132 views

### Sorting interleaved sorted lists

By interleaving two lists I mean to combine them into a single list in any way that maintains the relative order of the elements coming from each list. For example, interleaving $(x_1,x_2,x_3)$ and ...

**3**

votes

**1**answer

145 views

### How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

First some
Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...

**0**

votes

**0**answers

74 views

### Counting path generating sentences in a specific formal language

Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language?
For example, we know that if the grammar is context-free ...

**-1**

votes

**2**answers

427 views

### Can an algorithm decide whether a program computes all strings? [closed]

I am interested in the type of program, which is given as input to a Universal Turing Machine (UTM) with language $L$, and for which it holds that every possible finite string $s$ of symbols in $L$ ...

**0**

votes

**1**answer

233 views

### How to formalize “Is there a proof for every instance of the halting problem?”? [closed]

In a previous question that I asked here it turned out that for every instance of the halting problem, being the matter whether a certain computer program halts or runs forever, there exists a ...

**0**

votes

**1**answer

207 views

### Is there a consistent theory for each instance of the halting problem?

I got a bit confused by a discussion about the provability of the Goldbach conjecture and the seemingly different opinions about this subject. Since I understand computer science better, I will ask my ...

**0**

votes

**0**answers

137 views

### Trilateration issues, when circles don't intersect

I'm working on Indoor localization where I've deployed multiple iBeacons in my environment. I'm taking distances from all the beacons through their RSSI values. They are not 100% accurate though. Now ...

**0**

votes

**0**answers

34 views

### How can be a conservative field constraint be efficiently implemented in a continuous optimization problem?

Suppose we have the following continuous optimization problem:
$$
\underset{x}{\mathrm{minimize}}f\left(x\right)
$$
subject to
$$
\exists X:\nabla X=Jac\left(X\right)=x
$$
where $f$ is a function ...

**1**

vote

**1**answer

213 views

### Concept of synchronizability

This thread is about the concept of synchronizability. It's a concept I tried to formalize in its most general sense but without success. The goal of this thread is therefore to try to formalize it in ...

**5**

votes

**2**answers

185 views

### Can this way of comparing numbers of the form a+b sqrt(K) be generalized?

So I want to make a system for computing with various classes of numbers. One of those is a class of number closed under the standard arithmetic operators ($+$, $-$, $*$ and $/$) along with square ...

**8**

votes

**1**answer

132 views

### Reconstructing a string from random samples

What is known about the following problem?
Reconstruct a string $\sigma$ of known length $n$ over a known
alphabet $\Sigma$ from a collection of uniformly and independently
chosen $k$-long ...

**1**

vote

**0**answers

57 views

### Is there an efficient algorithm for sampling from the negative hypergeometric distribution? [closed]

I'm writing a small statistics library currently. One of the algorithms I'm implementing has two variants: one that samples the hypergeometric distribution and one that samples the negative ...

**3**

votes

**2**answers

341 views

### When does the greedy change-making algorithm work?

The change-making problem asks how to make a certain sum of money using the fewest coins. With US coins {1, 5, 10, 25}, the greedy algorithm of selecting the ...

**6**

votes

**2**answers

102 views

### scott continuity, sub additivity

Let $(X, \sqsubseteq_x)$ and $(Y, \sqsubseteq_y)$ be two posets and let $\delta_x:X \to X$ and $\delta_y:Y \to Y$ be two closure operators (monotone, inflationary, idempotent). Then, a monotone ...

**7**

votes

**2**answers

410 views

### A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image

I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 ...

**2**

votes

**2**answers

103 views

### Background for Kierstead terms

I was looking at some slides of John Longley's here, where he mentions "the Kierstead functional"
$$\lambda f.f(\lambda x.f(\lambda y.x)) \ ,$$
(where $f$ should be of type $2$, and $x,y$ of ground ...

**1**

vote

**1**answer

160 views

### Total conditional complexity

By $C(|)$ denote conditional complexity.
By $CT(|)$ denote total conditional complexity.
For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$
but $CT(x|y) \ge n $.
...

**-4**

votes

**1**answer

238 views

### An algorithm and symbolic manipulation for IF-THEN-ELSE [closed]

CONCLUSION (so far) Look at the parentheses theorem and at the comments below the question(s) :-) As for now, only Dan Peterson has truly addressed the issue.
Q1 Does there exists an ...

**8**

votes

**1**answer

231 views

### Compute an arbitrary decimal place of $\pi$

Is there a method to find the value of the $n$-th decimal place of $\pi$ which is more efficient than having to compute all decimal places before as well?

**0**

votes

**0**answers

53 views

### Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not.
Which software would you suggest for rigid transformations?
Thank you

**-2**

votes

**1**answer

272 views

### AI / Machine Learning related to high/modern/front mathematics [closed]

I major math and cs. and i'm interested in ai/machine learning/data mining.
so i want to know what math subjects are used in frontier of these technology.
especially, high mathematical tool, like ...

**2**

votes

**0**answers

92 views

### Mean Capture time for the Rabbit-Hunter paper by Peres et al [closed]

I am a non-math student. I am trying to read the paper "Hunter, Cauchy Rabbit, and Optimal Kakeya Sets" by Yuval Peres et al.
Link - http://arxiv.org/abs/1207.6389
In his video based on the paper - ...

**3**

votes

**1**answer

172 views

### internal language for the 2-category of small categories

What is the internal language of the category Cat of small categories?
I found an article by Glynn Winskel and his student Mario Jose Cáccamo about such calculus! However it is limited to a fragment ...

**1**

vote

**1**answer

96 views

### A certain instance of the Set Covering problem

Is there any useful structure associated with the following instance of the Set Covering problem?
Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all ...

**1**

vote

**1**answer

50 views

### How to select a subset of points from a universal to minimize the distance from outside to inside?

Here is the detailed problem.
I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as
$$ ...

**2**

votes

**2**answers

424 views

### Given a formal power series ,decide whether there exists a polynomial the series satisfies and if it exists,how to write it down?

Given a formal power series $$y(x)=\sum_{i=0}^{\infty} a_i x^i$$ Is there an algorithm that decides whether there exists a polynomial$$ P(x,y)=p_n(x)y^n+p_{n-1}(x)y^{n-1}+\cdots+p_0(x)=0,p_j(x)\in ...

**15**

votes

**3**answers

604 views

### Which distributions can you sample if you can sample a Gaussian?

Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...

**3**

votes

**1**answer

115 views

### A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.
The new problem is this. There is a tourist who has a having the following ...

**9**

votes

**1**answer

358 views

### Fast checking that overdetermined polynomial system does not have a solution

As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is ...

**4**

votes

**0**answers

141 views

### Correspondence between numerical semigroups and polynomials?

A numerical semigroup $A$ is defined as a subsemigroup of the semigroup $(\mathbb{N},+)$ of the positive integers such that the set $\mathbb{N}\setminus A$ is finite. Equivalently (for a subsemigroup) ...

**1**

vote

**1**answer

79 views

### Connection between inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...

**13**

votes

**1**answer

292 views

### Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...

**2**

votes

**0**answers

33 views

### largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature.
Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...

**4**

votes

**1**answer

142 views

### Which automated theorem provers can address the combinatorics of periods in strings?

Five years ago, I made a conjecture on the number of correlation classes that are exhibited by pairs of words in an alphabet of a given size. I later speculated that the conjecture could be tackled ...

**5**

votes

**1**answer

281 views

### Number of partitions whose blocks form arithmetic progressions

As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...