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 …

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 …

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 …

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 …

Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?

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 …

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 & …

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 …

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 …

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 …

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 …

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 …

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 …

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 …

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 …