For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.
0
votes
0answers
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
0answers
138 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
0answers
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 ...
3
votes
1answer
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 ...
2
votes
0answers
55 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
2answers
430 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
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
2answers
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
1answer
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
1answer
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 ...
0
votes
0answers
85 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
0answers
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 ...
1
vote
1answer
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 ...
5
votes
2answers
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
1answer
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 ...
1
vote
0answers
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
2answers
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 ...
5
votes
2answers
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 ...
7
votes
2answers
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
2answers
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 ...
1
vote
1answer
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 $.
...
-4
votes
1answer
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 ...
8
votes
1answer
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?
0
votes
0answers
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
1answer
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
0answers
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
1answer
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 ...
1
vote
1answer
91 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
1answer
40 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
2answers
419 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
3answers
586 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
1answer
113 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
1answer
343 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
0answers
135 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
1answer
75 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
1answer
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 ...
2
votes
0answers
31 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
1answer
129 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
1answer
276 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$. ...
1
vote
1answer
115 views
How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?
I am trying to solve:
Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle.
I only care about the asymptotic ...
4
votes
1answer
132 views
Self-similarity in the theory of computability
Let $M = w_0w_1... \in \{0,1\}^*$.
For any computable function $f$ define $M_f = w_{f(0)}w_{f(1)}...$
Let for any computable strictly increasing function $f$ there is continuous
computable mapping ...
2
votes
0answers
51 views
Private Randomness extractor
Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if ...
42
votes
1answer
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 ...
4
votes
1answer
344 views
Fundamental Problems in Mathematics that, without Computer Sciences, would not be resolved? [closed]
Could you please give examples of fundamental questions in mathematics (let us say, pure mathematics) which were resolved fundamentally by the use of computers? More precisely, are there examples that ...
6
votes
1answer
125 views
Separating infinite words sharing factors by automata
Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.
Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and ...
62
votes
2answers
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 ...
5
votes
1answer
82 views
Generalising the adherence operator and its closure properties with regard to regular (rational) languages
Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some ...
