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

32
votes
12answers
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? ...
1
vote
0answers
26 views

Determine existence of matroid with some barrier given

Let $E$ be a finite ground set. Let $\mathcal{L}$ (as lower barrier) and $\mathcal{U}$ (upper) be subsets of $2^E$. How can we determine whether there is some matroid $\mathcal{M}=(E,\mathcal{I})$ ...
4
votes
1answer
287 views

an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$. I mean there is polynomial reduction $F$ such that for every boolean ...
4
votes
5answers
7k 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 primitive recursive, but I ...
4
votes
1answer
106 views

Nearly Be Bruijn sequences constructed from De Bruijn sequences

Let $w$ be a De Bruijn $01$-sequence of the type $B(2,n)$; i.e., a cyclic $01$-sequence that contains every $n$-digit $01$-sequence exactly once. Let $x$ be a $01$-sequence of length $n$. When and ...
1
vote
2answers
45 views

Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution ...
1
vote
0answers
93 views

Expressing Numbers with a Minimal Sum in Powers of 2 [closed]

The first 64 bits of pi are: 11.00100100001111110110101010001000100001011010001100001000110100 Computer multiplication can be sped up by looking for patterns and ...
1
vote
0answers
44 views

Discrete Mathematics Uses [closed]

I am trying to explain how and why discrete maths is used in areas such as programming, correctness, data types, state transistion and conditionals. I'm having a really hard time articulating it ...
0
votes
0answers
31 views

Comparing product of positive affine functions over integers

Problem Let $f_i: \mathbb Z^n \mapsto \mathbb Z$ and $g_i: \mathbb Z^n \mapsto \mathbb Z$ affine functions and $\mathcal D \subseteq \mathbb Z^n$ a set on which they are all positive. Let $P$ and $Q$ ...
3
votes
1answer
87 views

How to get $\omega$-regular expression from buchi automaton

Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions? It is extremely ...
5
votes
2answers
160 views

How to construct particular De Bruijn sequences

For $n \ge 2$, there is at least one binary DeBruijn sequence beginning with $n$ zeros followed by $n$ ones. Is there a straightforward way to construct such a sequence for each $n \ge 2$? Examples: ...
-1
votes
1answer
837 views

Transition Graph per alphabet? [closed]

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
5
votes
2answers
236 views

What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title: What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space? Imagine I have some non-convex polyhedron $P$, and I would like to ...
1
vote
0answers
154 views

“Kolmogorov complexity” of models of computation

This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...
52
votes
3answers
4k 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 ...
2
votes
1answer
597 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
0
votes
0answers
33 views

Concrete examples of ODEs/PDEs arising in proofs in Complexity Theory and other subfields of CS

Can someone give me specific examples, (if and) where ODEs/PDEs arise in subfields of computer science ? What I'm not looking for are examples from numerical analysis or parts of computer science, ...
2
votes
1answer
309 views

A morphism-revealing category? [closed]

The constructs can be considered as subcategories of Set but when considered as subcategories of the category SubSet, of pairs of sets with pairs $(X,S)$, $S\subseteq X$, as objects and functions ...
6
votes
1answer
171 views

Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult. Is there a polynomial analog of this problem ...
6
votes
0answers
178 views

Complexity of approximating the size of the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$ It is NP-hard to compute $S_M$ exactly I believe by applying the ...
4
votes
0answers
134 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$ ...
11
votes
2answers
3k views

All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it. Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...
22
votes
8answers
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 ...
8
votes
1answer
424 views

How is Ricci flow related to computer graphics?

I recently came across the book Ricci Flow for Shape Analysis and Surface Registration: Theories, Algorithms and Applications by Wei Zeng and Xianfeng David Gu. Because, I just saw the book on the ...
16
votes
1answer
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 ...
6
votes
0answers
135 views

Does the Mandelbrot set have infinite VC dimension?

Define a binary classifier for points in the complex plane, whose parameter $\theta$ is an isometry of $\mathbb{C}$, and which classifies $z \in \mathbb{C}$ based on whether or not $\theta(z)$ is in ...
7
votes
1answer
113 views

Efficient SVD of a matrix without some of the columns

I have a matrix $A \in \mathbb{R}^{p \times q}$ of rank $r$ and its SVD decomposition, i.e, $$ A = U S V^\top, $$ where $U \in \mathbb{R}^{p \times r}$ and $V \in \mathbb{R}^{q \times r}$ are ...
2
votes
2answers
263 views

Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
5
votes
1answer
124 views

Monoidal cats and string diagrams for a semantics of object oriented programming languages

It seems to me that in a statically typed, object oriented language, there is a striking similarity to wiring diagrams. Wires (objects) of type $X$ go into functions (boxes) of input type $X$. Is ...
5
votes
0answers
113 views

Nonclassical polynomials, circles, and groups

Tao and Ziegler have introduced a generalization of polynomials over a prime field called nonclassical polynomials, useful for studying the Gowers norm. A nonclassical polynomial of degree $d$ is a ...
16
votes
1answer
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 ...
12
votes
1answer
4k views

Meaning of $\Subset$ notation

The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...
3
votes
1answer
208 views

Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...
14
votes
2answers
467 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 ...
11
votes
2answers
2k views

Best-case Running-time to solve an NP-Complete problem

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...
0
votes
2answers
496 views

What is a maximal set in the context of argumentation in AI [closed]

I am computer scientist, not a mathematician, I've been reading some papers on argumentation in AI that uses the term 'maximal' set without defining it. I think it's left undefined because it's a ...
4
votes
1answer
77 views

What class of probability distributions do probabilistic turing machines induce? [closed]

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?
13
votes
0answers
139 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 ...
5
votes
1answer
438 views

The relationship between P vs NP problem and “Kolmogorov complexity with time”

Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$. Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?" Is it Problem1 $\in ...
0
votes
0answers
420 views

Extended definition of unambiguous language and the existence of unambiguous grammar

Let's extend the unambiguity of language and grammar as follows: a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or ...
1
vote
0answers
39 views

Canonical representation of binary decision trees in Ptime?

I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence. More ...
3
votes
1answer
133 views

Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent? Is there any group for which we suspect them to be different? Could there be a finite ...
53
votes
4answers
6k 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 } ...
1
vote
0answers
28 views

Open volumetric time series data set

Does anyone know where I can find a good open volumetric time series data set? I had a look at some of Stanford's open data sets (https://graphics.stanford.edu/data/voldata/ ) But these do not seem ...
7
votes
1answer
171 views

“Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following: Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...
16
votes
3answers
729 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 ...
1
vote
0answers
67 views

Optimal reduction using token-passing nets

I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis ...
5
votes
0answers
111 views

Constructive Mathematics and Termination [closed]

In the book "The Universal Turing Machine A Half-Century Survey" there is a paper called "The Confluence of Ideas in 1936" by Robin Gandy. In section 4.2, Gandy writes: "If one accepts, on whatever ...
1
vote
1answer
90 views

floating point representation via the perspective of TTE/computable analysis

Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...
29
votes
13answers
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. ...