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

**6**

votes

**1**answer

81 views

### Embedding Turing machine [closed]

I have some questions about Turing machines. Is there an embedding method where you embed Turing machines, finite automata into continuous space or graphs? Or are there geometrical approaches to ...

**6**

votes

**3**answers

821 views

### Are there logical systems where formal proofs are not computer verifiable?

In a set-theoretic system using first-order logic, every proof could be written as a goal followed by a finite sequence of sentence where each one is justified by an axiom or previously established ...

**10**

votes

**1**answer

514 views

### Terminology: algebraic structure for “floating point” arithmetic

"floating point arithmetic" is a terminology that refer to the arithmetic perform over (finite) representation of real number. See the wikipedia article for more details.
In the formal specification ...

**1**

vote

**0**answers

65 views

### What is the value of a polynomial form for a data structure, aka a Container

Data structures like Lists and Trees are often referred to as Containers. They can be given as monads and containers are polynomial functors. The List monad is well known and can be given as a ...

**15**

votes

**8**answers

741 views

### Combinatorial constructions found by computer

In preparation for a talk I am giving to our undergraduate mathematics society, I am trying to collect examples of combinatorial constructions that were found by computer. Thus my question is the ...

**2**

votes

**1**answer

76 views

### Combinatorial problem about binary arrays with certain mutual distinctions

If there are m binary arrays (with 0 and 1) of length n, and between any two of these m arrays, there are k and only k same numbers (with the same site index in two different arrays). For example, if ...

**2**

votes

**1**answer

48 views

### Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra

Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...

**2**

votes

**0**answers

56 views

### Recovering a rank-one matrix from its eigendecomposition after randomized rounding

Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...

**38**

votes

**1**answer

746 views

### How to be rigorous about combinatorial algorithms?

1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...

**3**

votes

**1**answer

101 views

### Is every complete bounded finite lattice equivalent to a sublattice of a powerset lattice?

More precisely, if I have a complete bounded finite lattice $C$, can I compute a lattice-operation-preserving map $C \to P(S)$? for some $S$. If not, is there another universal lattice structure that ...

**2**

votes

**1**answer

121 views

### Is this cycling problem computable?

We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they ...

**13**

votes

**2**answers

2k views

### Who first chose the names Alice and Bob for players A and B? [closed]

Who first chose the names Alice and Bob for the players (or observers) A and B?

**2**

votes

**0**answers

84 views

### Transformation from the Bag monad to the List monad

The bag monad, sometimes called the multiset monad or free commutative monoid monad is a functor on Set that takes a set to its set of bags. These bags are like strings written in the elements of the ...

**6**

votes

**0**answers

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

**11**

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

**3**

votes

**0**answers

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

**10**

votes

**0**answers

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

**7**

votes

**1**answer

588 views

### graph signal processing

I have read this article
https://arxiv.org/abs/1307.5708
about vertix-frequency analysis on graph.
David IShuman
in this article claims that,"we generalize one of the most important signal ...

**1**

vote

**1**answer

158 views

### How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?

I am interested in a quantum algorithm that has the following characteristics:
output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits)
the number of 1-bits in the first set of n-bits must be equal ...

**1**

vote

**1**answer

50 views

### Existence of dense graph with relatively small codegree?

Let $n$ be some parameter tending to infinity. I am wondering does there exists some kind of graphs $G$ on vertex-set $[n]$ with maximum degree less than $D$, so that
$D\ge n/w_1(n)$,
$e_G$, the ...

**0**

votes

**0**answers

9 views

### How to square the (approximate) model count of a cnf formula?

Suppose I have a cnf formula (say $F$ with $n$ solutions) and an approximate model counter which gives
c-factor result (i.e. the actual count lies between $1/2^c$ to $2^c$ times the value returned).
...

**1**

vote

**0**answers

46 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)$ ...

**13**

votes

**1**answer

747 views

### What is Chemlambda? In which ways could it be interesting for a mathematician?

I${}^{*}$ have randomly come across a couple of websites (Chemlambda project, chorasimilarity) that seem to be about a certain "thing" (a computer program, I think) called Chemlambda that does "stuff" ...

**21**

votes

**1**answer

574 views

### What, mathematically speaking, does it mean to say that the continuation monad can simulate all monads?

In various places it is stated that the continuation monad can simulate all monads in some sense (see for example http://lambda1.jimpryor.net/manipulating_trees_with_monads/))
In particular, in http://...

**1**

vote

**1**answer

71 views

### Probability of collision of sums of vectors multiplied by random matrix

Let $S$ and $T$ be sets of vectors from $\mathbb{R}^d$ such that $S$ and $T$ are at least different in one element.
Does there exist a random matrix $M \in \mathbb{R}^{d \times k}$, e.g., a gaussian ...

**0**

votes

**0**answers

33 views

### Is this the best primality test using second order recurrences (Lucas Sequences)?

this is the copy of the question asked at mathematics stack exchange. original question https://math.stackexchange.com/q/2705983/469085
little Explanation
Using second order lucas sequences
$$U_{n +...

**2**

votes

**1**answer

46 views

### For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset

Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state ...

**1**

vote

**0**answers

35 views

### Is there a problem that can be solved in each of a nested sequence of resource constraints, but not in their intersection?

For example, is there a problem such that $\forall\varepsilon>0$ there is a $O(n^{1+\varepsilon})$-time algorithm to solve it, but which cannot be solved by a single algorithm which runs in $O(n^{1+...

**10**

votes

**1**answer

428 views

### Representing field elements in a computer

I'm wondering if there is existing terminology to describe fields $F$ with the properties below. I don't have a completely precise description of the concept I have in mind, but hopefully this will be ...

**2**

votes

**0**answers

72 views

### First appearance of “structure tree”?

Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...

**3**

votes

**1**answer

153 views

### Non-trivial parity maps in graphs

(This question actually arose in real life when dealing with status bits with mutual influence.)
Let $G=(V,E)$ be a connected, simple, undirected graph with $|V| \geq 2$. For $v\in V$, let $N_G(v) = \...

**20**

votes

**3**answers

554 views

### Defining computable functions categorically

Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...

**3**

votes

**0**answers

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

**2**

votes

**0**answers

48 views

### Maximum number of edges on $2^{k-1}+s$ vertices of a $k$-dimensional cube?

Let $k$ be an even number. For a $k$-dimensional cube (http://mathworld.wolfram.com/HypercubeGraph.html) $Q_k$, let $G$ be a subgraph of $Q_k$ with $2^{k-1}+s$ vertices, for $1\le s\le 2^{k-1}-1$. I ...

**2**

votes

**0**answers

125 views

### What are the axioms of the diagrammatic calculus for containers?

Ahman et al. wrote about when a container is a comonad. Containers can also be monads, such as List. This means that we can take all containers that are endofunctors on Set and they live in the ...

**2**

votes

**1**answer

253 views

### What is the (Co)Monad for a Bag

A Bag is a data structure, like a list, that stores items with no concept of order. The only operations on the structure is to add an item and then iterate through the items with no guarantee as to ...

**5**

votes

**1**answer

133 views

### A “dense” extension of the set of primitive recursive functions

Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...

**1**

vote

**0**answers

64 views

### Is there a complete countable axiomatization of conditional independence? (Graphoids)

Note: A pointer to a reference, or a yes/no answer with a 1-2 sentence incomplete/non-rigorous justification would suffice for answers. I am just curious about whether the result is true; it is fairly ...

**7**

votes

**1**answer

174 views

### Most efficient reductions between NP-complete problems

Assume I need to solve an NP-complete problem, for which problem-specific methods (e.g. efficient heuristics or exponential algorithms faster than naive one) are not well developed. If the size of ...

**12**

votes

**2**answers

292 views

### Automated search for bijective proofs

In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...

**1**

vote

**1**answer

293 views

### Is there any “fundamental” distinction between min-plus, max-plus, min-product, and max-product algebras?

In the paper Faster Algorithms for Max-Product Message Passing by McAuley and Caetano (see e.g. here or here), several statements are made which seem mathematically questionable to me.
For ...

**2**

votes

**2**answers

225 views

### Connection between countable ordinals and Turing degrees

$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...

**3**

votes

**0**answers

157 views

### Applications of logic in theoretical and practical Computer Science [closed]

Can anyone suggest theoretical and/or practical applications of logic (modal, dynamic, Lukasiewici etc.) in Computer Science (like Markov Chains for linear algebra), as well as some open-source books ...

**1**

vote

**0**answers

40 views

### Congruency check for set of points in 3D using inertia tensor

You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and ...

**1**

vote

**2**answers

144 views

### Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$

Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...

**1**

vote

**2**answers

59 views

### Is there a feasible way to compute the number of steps between two sequences generated by a linear feedback-shift register?

Consider a full-period LSFR with a feedback polynomial of degree n. In the cyclic sequence generated by the LSFR, each n-bit sequence appears exactly once. Given two n-bit sequences, one can define ...

**4**

votes

**0**answers

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

**7**

votes

**1**answer

235 views

### Spanning $k$-trees

k-trees
A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)
a) A complete graph with $k$ vertices is a $k$-tree.
b) A $k$-tree on $n$ vertices $T$ is obtained by a $...

**17**

votes

**3**answers

853 views

### Can you consistently add axioms about the Busy Beaver function to ZF?

Consider a Turing Machine with $N$ states which checks all theorems of ZF and halts upon finding a contradiction. If ZF were consistent and could prove the value of $BusyBeaver(N)$, then it would be ...

**2**

votes

**3**answers

204 views

### Efficiency of representations of number

In everyday practice the most common ways to represent integers are the binary and decimal systems. We use floating point or fixed point systems to (approximately) represent the reals. There are some ...