# Tagged Questions

**63**

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

**53**

votes

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

**52**

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

**48**

votes

**3**answers

3k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this ...

**46**

votes

**4**answers

2k views

### What algorithm in algebraic geometry should I work on implementing?

This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I ...

**46**

votes

**1**answer

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

**41**

votes

**30**answers

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

**33**

votes

**9**answers

4k views

### What is the shortest program for which halting is unknown?

In short, my question is:
What is the shortest computer program for which it is not known whether or not the program halts?
Of course, this depends on the description language; I also have the ...

**33**

votes

**7**answers

3k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...

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

**29**

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

**29**

votes

**0**answers

745 views

### Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories?
Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep ...

**28**

votes

**17**answers

8k views

### Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scienctists post questions looking to learn things ...

**27**

votes

**7**answers

7k views

### Problems known to be in both NP and coNP, but not known to be in P

One such problem I know is integer factorization.
What are other interesting cases?

**26**

votes

**10**answers

3k views

### Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not.
Are there some large $n$ ...

**26**

votes

**3**answers

2k views

### “Simpler” statements equivalent to Con(PA) or Con(ZFC)?

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...

**25**

votes

**11**answers

2k views

### Interesting conjectures “discovered” by computers and proved by humans?

There are notable examples of computers "proving" results discovered by mathematicians, what about the opposite:
Are there interesting conjectures "discovered" by computers and proved by humans?
...

**24**

votes

**4**answers

1k views

### A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others?
I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...

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

**23**

votes

**2**answers

3k views

### Counting subgraphs of bipartite graphs

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!
Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...

**22**

votes

**8**answers

2k views

### Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough
to express all functions, Ackermann function being probably the best
known example.
Now, in the logic courses (that I have had look ...

**22**

votes

**3**answers

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

**20**

votes

**4**answers

2k views

### Algorithmically unsolvable problems in topology

This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...

**19**

votes

**13**answers

7k views

### Programming Languages based on Category Theory

Since some computer scientists use category theory, I was wondering if there are any programming languages that use it extensively.

**19**

votes

**4**answers

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

**19**

votes

**2**answers

973 views

### Expected edit distance

The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example ...

**18**

votes

**4**answers

900 views

### Kolmogorov complexity is the strongest noncomputable function

Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...

**18**

votes

**3**answers

3k views

### Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...

**18**

votes

**0**answers

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

**16**

votes

**5**answers

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

**16**

votes

**1**answer

3k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...

**16**

votes

**1**answer

1k views

### Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...

**16**

votes

**1**answer

1k views

### What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...

**16**

votes

**3**answers

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

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

**15**

votes

**3**answers

898 views

### How do we express measurable spaces using type theory?

A measurable space $(X,\mathcal X)$ consists of a set $X$ equipped with a $\sigma$-algebra of subsets $\mathcal X$. I would like to write computer programs involving measurable spaces, but to the best ...

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

**15**

votes

**3**answers

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

**15**

votes

**2**answers

2k views

### Structure theorems for Turing-decidable languages?

Languages decidable by weak models of computation often have certain necessary characteristics, e.g. the pumping lemma for regular languages or the pumping lemma for context-free languages. Such ...

**14**

votes

**2**answers

451 views

### Can a stochastic Turing machine output a consistent extension of PA with positive probability?

Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...

**14**

votes

**2**answers

2k views

### Switching from pure mathematics (e.g. geometry) to more applied areas (e.g imaging) after Ph.D., as postdoc and chance of getting such a postdoc?

Before I start my question, I should probably mention that this question might not be the right question to ask here, but I tried academiabeta, and stackoverflow, but without getting any to-the-point ...

**14**

votes

**2**answers

2k views

### How to compute the rank of a matrix?

Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.
Here's the actual ...

**13**

votes

**6**answers

1k views

### SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...

**13**

votes

**2**answers

1k views

### Why is Kleene's notion of computability better than Banach-Mazur's?

In this post about the difference between the recursive and effective topos, Andrej Bauer said:
If you are looking for a deeper explanation, then perhaps it is fair to say that the Recursive Topos ...

**13**

votes

**8**answers

2k views

### How Does Random Noise Typically Look?

How does random noise in the digital world typically look?
Suppose you have a memory of n bits, and suppose that a "random noise" hits the memory in such a way that the probability of each bit being ...

**13**

votes

**1**answer

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

**13**

votes

**1**answer

507 views

### Bipartite Nim-Geography

Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...

**13**

votes

**0**answers

135 views

### Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...

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

**12**

votes

**2**answers

526 views

### What do you use categorical glueing/sconing/Freyd covers for?

In the theory of programming languages and structural proof theory, one of the handiest techniques we have available is a method called "logical relations", in which you can prove properties of ...