**0**

votes

**0**answers

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

**0**

votes

**0**answers

40 views

### multiple private keys for single public key [on hold]

I am currently working in security in mobile ad-hoc networks I have several clusters, and I want from the cluster head to send some data encrypted with its public key ,to the cluster members. I assume ...

**2**

votes

**0**answers

140 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

**0**answers

44 views

### A given graph Not Hamitonian is in NP Class? [closed]

From this book and other study in complexity theory, I have seen the following statement:
The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is ...

**1**

vote

**1**answer

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

**3**

votes

**1**answer

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

**4**

votes

**2**answers

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

**3**

votes

**0**answers

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

**24**

votes

**11**answers

2k views

### Where have you used computer programming in your career as an (applied/pure) mathematician?

For background: I'm working on a book to help mathematicians learn how to program. However, I need to see some examples from people in the field that have done different kinds of things than I have.
...

**5**

votes

**2**answers

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

**10**

votes

**6**answers

1k views

### Giving $Top(X,Y)$ an appropriate topology

I am not sure if its OK to ask this question here.
Let $Top$ be the category of topological spaces. Let $X,Y$ be objects in $Top$.
Let $F:\mathbb{I}\rightarrow Top(X,Y)$ be a function (I will ...

**14**

votes

**3**answers

2k views

### What is the history of the Y-combinator?

Inspired by the comments to this question, I wonder if someone can explain the history of the fixed point combinator (often called the Y combinator) in lambda calculus.
Where did it first appear? ...

**16**

votes

**3**answers

1k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**42**

votes

**1**answer

2k views

### Wanted: a “Coq for the working mathematician”

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar ...

**3**

votes

**1**answer

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

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

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

**3**

votes

**1**answer

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

**14**

votes

**5**answers

569 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**0**

votes

**0**answers

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

**15**

votes

**8**answers

1k views

### Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...

**1**

vote

**1**answer

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

**-1**

votes

**2**answers

416 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

231 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

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

**62**

votes

**2**answers

2k views

### How feasible is it to prove Kazhdan's property (T) by a computer?

Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually ...

**3**

votes

**11**answers

4k views

### Your experience of Computer Science/Programming in Mathematics Education? [closed]

This is a survey question, which seeks to produce a list of answers from the audience of mathematicians.
Motivation: I'm doing research in mathematics education. I'm particularly interested in ...

**38**

votes

**30**answers

40k views

### What programming languages do mathematicians use? [closed]

I understand this might be a slightly subjective question, but I am honestly curious what programming languages are used by the mathematics community.
I would imagine that there is a group of ...

**0**

votes

**0**answers

87 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

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

**5**

votes

**2**answers

168 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

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

**13**

votes

**1**answer

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

**5**

votes

**2**answers

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

**11**

votes

**3**answers

650 views

### Deciding membership in a convex hull

Problem: Given points $u,v_1,\dots,v_n\in\mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1,\dots,v_n.$
This can be done efficiently by linear programming (time polynomial in ...

**1**

vote

**0**answers

49 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

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

**2**

votes

**0**answers

186 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...

**7**

votes

**2**answers

384 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

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

**2**

votes

**2**answers

419 views

### What structure has been found for functions with this relationship.

Given $f$ and $g$
$\forall x y. f(x) = f(y) \Longrightarrow f(g(x)) = f(g(y))$
Or equivalently
$ker\ f \subseteq ker\ (f \circ g)$.
Note: if $f$ is injective then this holds for any $g$.
...

**-4**

votes

**1**answer

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

**4**

votes

**2**answers

3k views

### Something like mathoverflow in other sciences [closed]

Are the sites similar to mathoverflow in other sciences related to mathematics? statistics, computer science, physics, economics, etc?
Let me explain what I mean by "similar": those are sites devoted ...

**1**

vote

**2**answers

840 views

### What is the right citation for the power iteration method to find eigenvalues?

What is the right citation for the power iteration method to find eigenvalues, if I want to cite the method in a paper? I've seen some Google PageRank references in this context. But Brin and Page ...

**4**

votes

**3**answers

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

**8**

votes

**1**answer

230 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?

**3**

votes

**1**answer

195 views

### Bezier Curves question

Hi everyone
I have a fairly simple question about bezier curves: can you represent n bezier curves that have been continuously joined together by a single bezier curve of degree 3n?
My instinct is ...

**-2**

votes

**1**answer

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

**1**

vote

**0**answers

89 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

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