**11**

votes

**1**answer

221 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

**0**answers

39 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

**0**answers

82 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

**1**answer

292 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

**1**answer

111 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

**2**answers

49 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

**0**answers

46 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

**0**answers

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

**0**answers

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

**1**answer

90 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

**2**answers

166 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

**0**answers

163 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

**0**answers

34 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

**1**answer

311 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

**0**answers

180 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

**1**answer

431 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

**1**answer

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

**0**answers

136 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

**0**answers

116 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

**1**answer

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

**2**answers

268 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

**2**answers

480 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

**3**answers

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 ...

**7**

votes

**1**answer

117 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

**1**answer

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

**1**answer

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 ...

**13**

votes

**0**answers

140 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

**1**answer

134 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

**0**answers

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 ...

**6**

votes

**1**answer

172 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

**0**answers

112 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

**1**answer

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 ...

**1**

vote

**1**answer

92 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

**0**answers

557 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

**1**answer

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

**0**answers

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

**0**answers

244 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 ...

**5**

votes

**2**answers

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 ...

**1**

vote

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**3**answers

961 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

**0**answers

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 ...

**11**

votes

**3**answers

760 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 ...

**6**

votes

**0**answers

251 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**1**

vote

**1**answer

309 views

### Functional programing and intensional type theory

I know very little about how computers work, so please excuse my ignorance!
I think of the Glasgow Haskell Compiler as a program that eats up extensional type theory and spits out a program which ...

**3**

votes

**0**answers

153 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**-4**

votes

**1**answer

152 views

### What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...

**6**

votes

**1**answer

1k views

### Constructing the oracle for Grover's algorithm

For a final project in my class, I decided to try to simulate a quantum computer and implement Grover's algorithm. I followed this excellently written blog post by Craig Gidney, and was successful in ...