# Questions tagged [computer-science]

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.

101
questions with no upvoted or accepted answers

**34**

votes

**0**answers

931 views

### Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories?
Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep track ...

**18**

votes

**0**answers

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

**14**

votes

**0**answers

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

**14**

votes

**0**answers

401 views

### Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...

**13**

votes

**0**answers

204 views

### Is the set of power matrices decidable?

Let $\text{Mat}(n\times n,\mathbb{Z})$ denote the collection of integer $n\times n$ matrices. We say $M\in \text{Mat}(n\times n,\mathbb{Z})$ is a power matrix if there is an integer $k>1$ and a ...

**11**

votes

**0**answers

452 views

### Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...

**10**

votes

**0**answers

127 views

### A combinatorial proof of the Harrow--Kolla--Schulman theorem

Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$.
For integers $0 \leq k \leq n$, define a ...

**9**

votes

**0**answers

1k views

### The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.
Are ...

**9**

votes

**0**answers

750 views

### Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another

Please consider the set of all possible strings of some finite size $M$ alphabet $\Sigma$, $\alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|\alpha| = L$. The Levenshtein distance (or 'edit ...

**8**

votes

**0**answers

1k views

### Question on randomness extractors

Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...

**7**

votes

**0**answers

229 views

### Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere

Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...

**7**

votes

**0**answers

3k views

### Is the conjecture A+B=C following correct?

Is the conjecture on A+B=C following correct ?
Conjecture: Let $A, B, C$ be three positive integer numbers such that $A+B=C$ with $\gcd(A, B, C) = 1$. By Fundamental theorem of arithmetic we write:
...

**7**

votes

**0**answers

310 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

**0**answers

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

**7**

votes

**0**answers

163 views

### Finding a database of representations as matrices

Sorry if this would be more appropriate as a stackoverflow and not a mathoverflow question, but I think it's more likely to be known in this community.
There are plenty of places on the internet or ...

**6**

votes

**0**answers

150 views

### Approximating a ray with an integer lattice point

Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r^2\}.$
With $\|\cdot \|$ the 2-norm, what is the distribution (or at least the ...

**6**

votes

**0**answers

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

**6**

votes

**0**answers

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

**6**

votes

**0**answers

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

**6**

votes

**0**answers

772 views

### How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective.
I am interested in the size of ...

**6**

votes

**0**answers

1k views

### Hash functions and inner product

As part of a research project on derandomization of linear threshold functions I am working on, I am trying to understand the following problem:
Is there a small (polynomial rather than exponential)...

**5**

votes

**0**answers

244 views

### What arithmetic would you do in parallel?

This is a post asking for references, and soliciting problems and people interested in accelerated computing. I will add the big-list tag and make it community-wiki. If this interests you strongly, ...

**5**

votes

**0**answers

187 views

### Quantum P vs NP equivalent problem

If $P = NP$, does it follow that $BQP = NP^{BQP}$?
I came up with this question when I was thinking about how $P = NP$ can be described as "does every decision problem where a proof for YES can be ...

**5**

votes

**0**answers

105 views

### A Combinatorial Problem on Extremal Set Theory

Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?
(i) $\forall S\in \mathcal{F}$, $|S|=a$....

**5**

votes

**0**answers

130 views

### Are there sampNP-intermediate problems?

This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \...

**5**

votes

**0**answers

342 views

### Chain/Hierarchy of Monoids

Let's assume that we have the following collection of structures:
Some space $P$.
Monoids $(M_{i+1},\circ_{i+1})$, and
Actions $\bullet_{i+1}:M_{i+1}\times M_i\to M_i$, for $i\ge 0$
And $\bullet_{0}:...

**4**

votes

**1**answer

125 views

### Polynomial size embeddings of toric varieties from polytopes?

Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.
$X_P$ is always projective, because the collection of characters corresponding to the points $\...

**4**

votes

**0**answers

118 views

### Is there any accepted single-word that means “partial function”?

When I'm explaining things involving partial functions, I usually end up stumbling over my words, like so: "Suppose $f : A \rightarrow B$ is a function, uhh, sorry I mean a partial function, and ...

**4**

votes

**0**answers

509 views

### Problems with the Bounded Envy-Free Cake Cutting Protocol of Aziz & Mackenzie [2016]

The problem I'm seeing is with Case 2 of Lemma 4.5 in the latest version of the ArXiv preprint:
Unallocated contested piece a has proper trims on it (recall that we
are ignoring part that is left ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

180 views

### Correspondence between numerical semigroups and polynomials?

A numerical semigroup $A$ is defined as a subsemigroup of the semigroup $(\mathbb{N},+)$ of the positive integers such that the set $\mathbb{N}\setminus A$ is finite. Equivalently (for a subsemigroup) ...

**4**

votes

**0**answers

499 views

### About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...

**4**

votes

**0**answers

195 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**4**

votes

**0**answers

179 views

### Question about constructing an admissible ideal of a quiver of an algebra with the aid of a computer

Let $k$ be an algebraically closed field and $A$ a finite-dimensional, basic, connected $k$-algebra. Then $A$ is Morita-equivalent to a quotient of a path algebra $kQ/I$ and $I$ is an admissible ...

**4**

votes

**0**answers

222 views

### Is it possible to implement η-reduction in interaction nets?

There are several ways to encode λ-terms in interaction nets; for instance, using the original optimal algorithm by Lamping, or compiling λ-calculus into interaction combinators. However, all the ...

**3**

votes

**0**answers

106 views

### Why does division parallelize but not continued fractions and is there an analog of multiplication to continued fractions?

All the basic arithmetic operations $\times,+,/,-$ can be parallelized. However continued fraction representation of a rational number is not parallelized. The process of Euclid's algorithm looks ...

**3**

votes

**0**answers

41 views

### Explicit, small resolving sets for Hamming graphs

Definition. Let $G = (V;E)$ be a finite, undirected graph. $R = \{r_1, \ldots, r_k \} \subseteq V$. $R$ resolves $G$ if
$$
V \to [0, \infty]^k, v \mapsto (d_G(v,r_1), \ldots, d_G(v, r_k))
$$
is ...

**3**

votes

**0**answers

235 views

### Upward confluence in the interaction calculus

The lambda calculus is not upward confluent, counterexamples being known for a long time. Now, what about the interaction calculus? Specifically, I am looking for configurations $c_1$ and $c_2$ such ...

**3**

votes

**0**answers

92 views

### Empirically random, quickly multiplicable matrices

I have encountered a need for fast computation of a transformation $Ax$ where $A\in \mathbb{C}^{K\times N},\ K\sim 10^7,\ N\sim 10^3$ is designed, and $x\in \mathbb{C}^N$ has iid $\mathcal{CN}(0,1)$ ...

**3**

votes

**0**answers

55 views

### Lattice basis reduction over rings of number fields

Can one use lattice basis reduction algorithms, such as LLL over (low-rank) module lattices over rings of number fields of degree greater than 1? Is there any work on lattice reductions over Euclidean ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

290 views

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

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

76 views

### Are all $k$th-longest-tour problems equally hard?

It is well known, that determining the shortest and, the longest Hamilton Cycle of a complete graph with real edge weights are algorithmically two sides of the same medal: one transforms to the other ...

**3**

votes

**0**answers

70 views

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...

**3**

votes

**0**answers

464 views

### Groupoid interpretation of type theory

Hello,
I read the paper on groupoid interpretation of type theory by Hofmann and Streicher and I have a question. According to the authors $Tm([[\text{Set}\:[\Gamma]\: ]])$ is the same as $\text{Se}([...

**3**

votes

**0**answers

297 views

### what is the largest gap between rank and approximate rank

$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...

**3**

votes

**0**answers

380 views

### Inversion density: Have you seen this concept?

Let $n > 1$ be an integer.
Let $A$ be an array, indexed from $1$ to $n$, of $n$ values
$A(i)$ coming from the finite set $\{0,1\}$.
(More generally, the values can come from any
totally ordered ...

**3**

votes

**0**answers

387 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 to analysis." What ...

**2**

votes

**0**answers

113 views

### Primitive recursive functions

Suppose $f_1, f_2, ... ,f_n$ is a finite list of primitive recursive functions.
Consider the set of terms $T$ that can be constructed from $f_1, .... , f_n$ and the constant $0$.
Consider the ...