3
votes
1answer
24 views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in …
0
votes
2answers
107 views
Find the subset of a line on a sphere “far” from a set of points on the sphere.
I have some code where the "hot part" relies on an inefficient solution to this problem.
Problem: I have 3 inputs:
a. A collection of N points on the surface of a sphere.
b. A l …
30
votes
3answers
394 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 geometr …
1
vote
1answer
104 views
Signed minimum?
I am looking for references to papers which might have defined a 'signed minimum' equivalent to
$$smin(x,y) ::= \left(\frac{\textit{signum}(x)+\textit{signum}(y)}{2}\right)\cdot \m …
0
votes
2answers
205 views
Travelling Salesman Problem
Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
7
votes
1answer
199 views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a ro …
0
votes
1answer
87 views
Decidable real arithmetic
I believe that what I'm about to describe has a name—I'm almost certain that I've seen this in model theory and term-rewriting systems, possibly having something to do with & …
4
votes
4answers
206 views
Prove a function is primitive recursive
Hey,
I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primit …
8
votes
3answers
400 views
Alive dynamical system
Intuitively, one can say that a dynamical system is alive if one can build a universal Turing machine inside.
So, Conway's Game of Life is alive and shift space should be dead.
I …
5
votes
0answers
72 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 …
12
votes
21answers
3k views
What programming languages do mathematicians use?
Ok 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 ther …
3
votes
0answers
214 views
Wolff’s application of CS to analysis
In the foreword of Tom Wolff's "Lectures on Harmonic Analysis", C. Fefferman writes "[Wolff made] (as far as I know) the first serious application of theoretical computer science t …
10
votes
1answer
321 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 …
9
votes
4answers
200 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 re …
5
votes
1answer
208 views
Finding unknown integer-valued polynomials using inequalities
I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here.
Suppose you …
