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
Filter by
Sorted by
Tagged with
34
votes
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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 ...