Questions tagged [computer-science]
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.
641 questions
14
votes
1
answer
11k
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 ...
CommunityBot
- 1
4
votes
1
answer
4k
views
How are taps proven to work for LFSRs?
Obviously, you can exhaustively check that it lands on every state except the zero state, but for large linear feedback shift registers (LFSR), this quickly becomes infeasible.
Wikipedia states the ...
- 6,210
4
votes
1
answer
248
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
$$
\text{coBHP}=\{\...
CommunityBot
- 1
1
vote
1
answer
185
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 $.
...
CommunityBot
- 1
1
vote
0
answers
89
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 ...
- 527
2
votes
1
answer
129
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, x_{3k+1},x_{3k+2},x_{3k+3})\in\...
- 171
1
vote
1
answer
139
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,1\...
- 2,576
4
votes
0
answers
312
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 ...
- 4,529
3
votes
0
answers
79
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 ...
- 29.8k
17
votes
3
answers
3k
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? ...
CommunityBot
- 1
3
votes
1
answer
620
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 $(...
- 1,676
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 ...
17
votes
5
answers
981
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
105
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 ...
- 38.6k
15
votes
7
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
248
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 ...
CommunityBot
- 1
-1
votes
2
answers
534
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$ ...
- 67
0
votes
1
answer
318
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 ...
- 67
1
vote
1
answer
383
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 ...
- 67
70
votes
30
answers
94k
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 ...
CommunityBot
- 1
5
votes
2
answers
253
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 ...
- 47.3k
8
votes
1
answer
158
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 ...
- 54.2k
4
votes
2
answers
263
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 ...
- 48.9k
1
vote
0
answers
179
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 ...
- 6,210
4
votes
2
answers
1k
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 ...
- 3,028
8
votes
2
answers
1k
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 ...
- 818
2
votes
2
answers
181
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 ...
- 269
2
votes
2
answers
528
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$.
...
CommunityBot
- 1
3
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 ...
CommunityBot
- 1
8
votes
1
answer
330
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?
- 19.6k
3
votes
1
answer
476
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 ...
- 649
0
votes
1
answer
2k
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 ...
- 28.6k
4
votes
1
answer
278
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 ...
- 66.8k
1
vote
1
answer
131
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 ...
12
votes
3
answers
1k
views
The difference between the Recursive and the Effective topos.
I would like to know which is the real difference between the Recursive topos (in the sense of Mulry) and the Effective topos (in the sense of Hyland). Especially what is related to recursive ...
- 32.5k
1
vote
1
answer
280
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
$$ d(...
- 2,966
5
votes
2
answers
901
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 F[x]...
- 6,397
1
vote
1
answer
205
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 ...
- 752
6
votes
3
answers
961
views
What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?
Let me begin with an example.
Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...
- 9,683
30
votes
1
answer
3k
views
An edge partitioning problem on cubic graphs
Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
CommunityBot
- 1
3
votes
1
answer
178
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 ...
- 757
10
votes
1
answer
595
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 ...
- 728
4
votes
0
answers
199
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) ...
CommunityBot
- 1
6
votes
1
answer
165
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 ...
CommunityBot
- 1
2
votes
0
answers
44
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 ...
- 1,109
6
votes
0
answers
805
views
How many 2L-bit numbers are the product of two L-bit numbers?
If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of ...
- 13.9k
9
votes
2
answers
2k
views
Busy Beaver - Proof for BB(2) = 4
Hi,
I need to prove the above claim.
I can show that $BB(2)\ge 4$ by building a turing machine,
but how can i show that $BB(2) \le 4$?
Searched a lot over the web, and saw that Rado proved it in ...
- 32.5k
6
votes
1
answer
352
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$. ...
- 43.7k
5
votes
1
answer
224
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 ...
- 56.9k
11
votes
2
answers
964
views
What Turing-Complete models of computation carry a notion of time complexity that "agrees" with that of Turing Machines?
Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive ...
CommunityBot
- 1