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.

Filter by
Sorted by
Tagged with
186 votes
3 answers
95k views

Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?

QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
user161819's user avatar
101 votes
4 answers
5k 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 can ...
Narutaka OZAWA's user avatar
96 votes
7 answers
19k 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 \...
Kaveh's user avatar
  • 5,362
81 votes
6 answers
11k views

Is data science mathematically interesting?

I have seen a plethora of job advertisements in the last few years on mathjobs.org for academic positions in data science. Now I understand why economic pressures would cause this to happen, but from ...
81 votes
4 answers
7k 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 with....
darij grinberg's user avatar
71 votes
10 answers
19k 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 ...
Michael Hoffman's user avatar
70 votes
30 answers
93k 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 ...
65 votes
4 answers
11k 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 week,...
64 votes
1 answer
4k views

How to be rigorous about combinatorial algorithms?

1. The question This may be the worst question I've ever posed on MathOverflow: broad, open-ended and likely to produce heat. Yet, I think any progress that will be made here will be extremely useful ...
darij grinberg's user avatar
56 votes
10 answers
7k views

A clear map of mathematical approaches to Artificial Intelligence

I have recently become interested in Machine Learning and AI as a student of theoretical physics and mathematics, and have gone through some of the recommended resources dealing with statistical ...
53 votes
17 answers
15k 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 scientists post questions looking to learn things ...
50 votes
8 answers
24k 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?
50 votes
4 answers
4k 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
7 answers
12k 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 ...
Ryan O'Donnell's user avatar
45 votes
4 answers
1k views

How to write computer-assisted mathematics well?

Much has been said about writting good papers in mathematics. A short google query yields countless sources of advice. This skill also appears to be quite transferrable between basic branches of ...
43 votes
4 answers
4k views

Lists as a foundation of mathematics

I am wondering if there is a foundation of mathematics where not sets or "set-like objects" (such as objects of a suitable topos as in ETCS) are the primitive notion, but rather lists. These ...
Martin Brandenburg's user avatar
43 votes
3 answers
5k 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 ...
Scott Aaronson's user avatar
41 votes
10 answers
7k 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 ...
Daniel Litt's user avatar
  • 22.2k
40 votes
16 answers
17k 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.
37 votes
12 answers
3k 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? ...
37 votes
0 answers
1k 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 track ...
Heinrich Hartmann's user avatar
35 votes
14 answers
4k 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. ...
35 votes
8 answers
3k views

Examples of errors in computational combinatorics results

I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
34 votes
9 answers
5k views

Decision problems for which it is unknown whether they are decidable

In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
34 votes
11 answers
3k views

Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
33 votes
3 answers
4k views

Using Busy Beavers to prove conjectures

I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
schnitzi's user avatar
  • 463
30 votes
1 answer
588 views

Guess that group via product queries

Suppose someone (person B) knows a finite group $G$ of order $n$. You (person A) know only the order $n$, and that $1$ is the name of the identity element. The group elements are named $1,2,\ldots,n$ ...
Joseph O'Rourke's user avatar
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 ...
Anthony Labarre's user avatar
29 votes
4 answers
2k 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 ...
user20886's user avatar
  • 483
27 votes
8 answers
4k 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 at)...
user avatar
27 votes
3 answers
2k views

Defining computable functions categorically

Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...
N. Virgo's user avatar
  • 1,316
27 votes
3 answers
2k 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 $$\operatorname{...
user avatar
26 votes
10 answers
4k 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$ ...
user40919's user avatar
  • 701
25 votes
1 answer
6k 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 ...
user16007's user avatar
  • 780
25 votes
4 answers
3k 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 ...
24 votes
3 answers
2k 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 ...
24 votes
4 answers
3k 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 ...
Adam's user avatar
  • 3,247
24 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 ...
AlastairK's user avatar
  • 291
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 ...
Stefan Kohl's user avatar
  • 19.5k
23 votes
1 answer
966 views

What, mathematically speaking, does it mean to say that the continuation monad can simulate all monads?

In various places it is stated that the continuation monad can simulate all monads in some sense (see for example http://lambda1.jimpryor.net/manipulating_trees_with_monads/)) In particular, in http://...
user65526's user avatar
  • 629
22 votes
9 answers
16k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
Nathann Cohen's user avatar
22 votes
1 answer
5k 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 ...
Symeof's user avatar
  • 323
21 votes
3 answers
6k 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 ...
Ryan Williams's user avatar
20 votes
2 answers
2k views

Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$

As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis. Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
20 votes
5 answers
1k views

Is there a natural family of languages whose generating functions are holonomic (i.e. D-finite)?

Let $L$ be a language on a finite alphabet and let $L_n$ be the number of words of length $n$. Let $f_L(x) = \sum_{n \ge 0} L_n x^n$. The following are well-known: If $L$ is regular, then $f_L$ is ...
Qiaochu Yuan's user avatar
20 votes
3 answers
1k 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 a ...
Tara Brough's user avatar
19 votes
4 answers
1k views

Kolmogorov complexity is the strongest noncomputable function

Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...
Alexey Milovanov's user avatar
19 votes
3 answers
1k 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 ...
Alex Zorn's user avatar
  • 902
19 votes
3 answers
1k views

Can you consistently add axioms about the Busy Beaver function to ZF?

Consider a Turing Machine with $N$ states which checks all theorems of ZF and halts upon finding a contradiction. If ZF were consistent and could prove the value of $BusyBeaver(N)$, then it would be ...
Richard Ngo's user avatar
19 votes
1 answer
2k views

What is Chemlambda? In which ways could it be interesting for a mathematician?

I${}^{*}$ have randomly come across a couple of websites (Chemlambda project, chorasimilarity) that seem to be about a certain "thing" (a computer program, I think) called Chemlambda that does "stuff" ...
Qfwfq's user avatar
  • 22.7k

1
2 3 4 5
13