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