**-1**

votes

**0**answers

13 views

### Similarity estimation

http://www.diku.dk/summer-school-2014/course-material/mikkel-thorup/bottomk-exercise.pdf Can somebody help with exercise 4 in chapter 2.2? Any hints would be highly appreciated.

**7**

votes

**1**answer

149 views

### “Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...

**16**

votes

**3**answers

680 views

### Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:
Find a decision procedure for determining if an arbitrary semilinear set
is ...

**2**

votes

**1**answer

159 views

### Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...

**0**

votes

**0**answers

51 views

### Optimal reduction using token-passing nets

I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis ...

**4**

votes

**0**answers

100 views

### Constructive Mathematics and Termination [closed]

In the book "The Universal Turing Machine A Half-Century Survey" there is a paper called "The Confluence of Ideas in 1936" by Robin Gandy. In section 4.2, Gandy writes:
"If one accepts, on whatever ...

**5**

votes

**1**answer

105 views

### Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Is there a polynomial analog of this problem ...

**0**

votes

**1**answer

38 views

### floating point representation via the perspective of TTE/computable analysis

Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...

**28**

votes

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

**9**

votes

**6**answers

2k views

### Aren't “oracle machines” unsound concepts? [closed]

From Wikipedia (bold emphasis at the end is mine):
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as ...

**17**

votes

**0**answers

516 views

### Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...

**-2**

votes

**1**answer

219 views

### Are limits decidable? Should definitions be decidable? [closed]

This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...

**1**

vote

**0**answers

98 views

### Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...

**2**

votes

**0**answers

220 views

### Possible $\mathsf{NP}$ complete problem from number theory

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem ...

**4**

votes

**2**answers

177 views

### If $f : [-a,a] \rightarrow \mathbb{IR}$ is Scott continuous, why are $f^-$ and $f^+$ measurable?

In "A domain theoretic account of Picard's theorem" (http://www.doc.ic.ac.uk/~dirk/Publications/icalp2004.pdf), the authors assert the following.
Let $\mathbb{IR}$ be the interval domain $\lbrace ...

**5**

votes

**0**answers

198 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**0**

votes

**1**answer

46 views

### Finding t vlaue in Bezier curve [closed]

According to this question, I'm looking for some method to find the t value in Quadratic bezier curve equation:
$$
B(t)=P_0+t(1-t)P_1+t^2P_2 \space \space where \space 0 ≤ t ≤ 1
$$
In this ...

**5**

votes

**1**answer

140 views

### Algorithm that generates a n-simplex that cover n-polytope?

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

**0**

votes

**0**answers

24 views

### Canonical representation of binary decision trees in Ptime?

I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence.
More ...

**21**

votes

**3**answers

800 views

### What technical and/or theoretical challenges are involved in automatically extracting proofs from books and papers into Coq code?

Over the years, advances in machine learning has allowed us to communicate and interact, using the same natural language, more and more semantically with computers, e.g. Google, Siri, Watson, etc. On ...

**0**

votes

**0**answers

45 views

### Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N ...

**6**

votes

**0**answers

144 views

### Distribution of trivial subset sums

Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...

**8**

votes

**3**answers

674 views

### Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...

**19**

votes

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

**1**

vote

**1**answer

273 views

### Functional programing and intensional type theory

I know very little about how computers work, so please excuse my ignorance!
I think of the Glasgow Haskell Compiler as a program that eats up extensional type theory and spits out a program which ...

**2**

votes

**0**answers

128 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**39**

votes

**3**answers

5k views

### Can we cover the unit square by these rectangles?

The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.
It is easy to show that
$$\sum_{1 \leq k } ...

**-4**

votes

**1**answer

134 views

### What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...

**4**

votes

**1**answer

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

**0**

votes

**1**answer

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

**11**

votes

**1**answer

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

**51**

votes

**9**answers

12k views

### Relating Category Theory to Programming Language Theory

I'm wondering what the relation of category theory to programming language theory is.
I've been reading some books on category theory and topos theory, but if someone happens to know what the ...

**4**

votes

**1**answer

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

**1**

vote

**1**answer

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

**2**

votes

**0**answers

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

**5**

votes

**2**answers

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

**1**

vote

**0**answers

71 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

319 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

109 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

85 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

183 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

598 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

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

**5**

votes

**2**answers

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

**12**

votes

**6**answers

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

**15**

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

**45**

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

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

**3**

votes

**1**answer

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