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

6
votes
1answer
265 views

What do we call this quantifier (“binder”)?

There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...
1
vote
0answers
44 views

computing homology of subvarieties of Euclidean spaces by persistent homology

Let $M$ be a submanifold of the Euclidean space $\mathbb{R}^n$. Let $G$ be a finite group acting on $M$ freely. I want to compute the homology (or even the cohomology ring) of $M/G$. Suppose the ...
2
votes
0answers
56 views

Effective “almost enumeration” of monotone boolean functions

Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$. Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that: 1) $k = \log |\...
11
votes
1answer
250 views

Digital physics and “Gandy-like” machines

Various physicists, famously John Wheeler, have asserted that physical information is the central object of study in physics, in the sense that an object or concept is "physically meaningful" if it ...
0
votes
0answers
43 views

Reconstructing a graph from set of sequences of edges

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
1
vote
0answers
117 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
295 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
1answer
112 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
51 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
47 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
33 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$ ...
1
vote
0answers
94 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 ...
3
votes
1answer
100 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
168 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
vote
0answers
165 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 ...
0
votes
0answers
36 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
314 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 $f:X\...
6
votes
0answers
183 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 ...
8
votes
1answer
437 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
139 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 ...
5
votes
0answers
118 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 ...
2
votes
2answers
272 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 ...
15
votes
2answers
492 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 ...
53
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 week,...
7
votes
1answer
119 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 ...
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?
5
votes
1answer
125 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 ...
14
votes
0answers
142 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 ...
3
votes
1answer
135 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 ...
1
vote
0answers
69 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 ...
6
votes
1answer
173 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 ...
5
votes
0answers
114 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 ...
7
votes
1answer
173 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 ...
1
vote
1answer
97 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 ...
18
votes
0answers
561 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 ...
-1
votes
1answer
252 views

Are limits decidable? Should definitions be decidable? [closed]

This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition: There cannot exist a Turing Machine $M$ which, given a ...
3
votes
0answers
108 views

Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
3
votes
0answers
245 views

Possible $\mathsf{NP}$ complete problem from number theory

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...
5
votes
2answers
182 views

If $f : [-a,a] \rightarrow \mathbb{IR}$ is Scott continuous, why are $f^-$ and $f^+$ measurable?

In "A domain theoretic account of Picard's theorem" (http://www.doc.ic.ac.uk/~dirk/Publications/icalp2004.pdf), the authors assert the following. Let $\mathbb{IR}$ be the interval domain $\lbrace [a^-...
1
vote
1answer
65 views

Finding t vlaue in Bezier curve [closed]

According to this question, I'm looking for some method to find the t value in Quadratic bezier curve equation: $$ B(t)=P_0+t(1-t)P_1+t^2P_2 \space \space where \space 0 ≤ t ≤ 1 $$ In this ...
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 ...
0
votes
0answers
47 views

Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N \...
1
vote
0answers
29 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 ...
23
votes
3answers
972 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 ...
7
votes
0answers
162 views

Distribution of trivial subset sums

Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...
12
votes
3answers
771 views

Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...