Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
3answers
733 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
1answer
506 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
0answers
61 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 ...
14
votes
8answers
706 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
1answer
75 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
1answer
47 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
0answers
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
1answer
690 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
1answer
90 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
1answer
120 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
2answers
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
0answers
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
0answers
132 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
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: ...
3
votes
0answers
219 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
0answers
103 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 ...
6
votes
1answer
506 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
1answer
153 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
1answer
49 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
0answers
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
0answers
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
1answer
719 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
1answer
553 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
1answer
70 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
0answers
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
1answer
44 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
0answers
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
1answer
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
0answers
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
1answer
152 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
3answers
535 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
0answers
47 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
0answers
47 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
0answers
124 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
1answer
246 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
1answer
131 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
0answers
62 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
1answer
168 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
2answers
287 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
1answer
275 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
2answers
222 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
0answers
154 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
0answers
39 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
2answers
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
2answers
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
0answers
165 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
1answer
229 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
3answers
844 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
3answers
201 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 ...
1
vote
0answers
81 views

What does homomorphism between languages mean to the correspoding Turing Machines?

According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the ...