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.

learn more… | top users | synonyms

9
votes
1answer
209 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 ...
5
votes
0answers
102 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
3answers
632 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
4answers
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 ...
4
votes
0answers
116 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 ...
1
vote
1answer
239 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
0answers
112 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 ...
38
votes
3answers
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
1answer
128 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
1answer
206 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
1answer
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 ...
5
votes
1answer
98 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
1answer
458 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
9answers
11k 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
1answer
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
1answer
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 $. ...
25
votes
12answers
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. ...
2
votes
0answers
82 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$ ...
4
votes
2answers
720 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
0answers
68 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
0answers
313 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
1answer
106 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
1answer
83 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
0answers
175 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
1answer
501 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
0answers
68 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
2answers
327 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
6answers
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
3answers
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? ...
44
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 ...
3
votes
1answer
156 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
5answers
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
0answers
54 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
1answer
147 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
5answers
587 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
0answers
78 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
8answers
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
1answer
218 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
2answers
430 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
234 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
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 ...
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 ...
3
votes
11answers
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
30answers
44k 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
0answers
148 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
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 ...
5
votes
2answers
190 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
134 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
1answer
303 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 ...
6
votes
2answers
105 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 ...