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.
496
questions
-2
votes
0answers
87 views
What am I doing with sparse and binary and what theorems should I look into? [on hold]
Forgive me, for I am not a professional. I'm working on a research project for my own empirical results based on repeatable observations and information from books.
My System for Sparse Strings
...
0
votes
0answers
67 views
A matching like problem
Consider finite sets S and R and a symmetric function $f:SxS\rightarrow R$. Let M be a matching, ie a partition of S into subsets of size 2. For each matching can count the number of pairs that map ...
0
votes
1answer
41 views
Distance of uniformly distributed point in n-dimensional unit ball [closed]
Let $B$ be the $n$-dimensional unit ball in the Euclidean space and $X_1,...,X_k$ be $k$ uniformly distributed points in $B$.
What is the distance between a pair of points for a given dimension $n$ ...
0
votes
1answer
119 views
Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]
Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
5
votes
1answer
159 views
Random walk on the hypercube with deleted edges
Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...
62
votes
6answers
8k views
Is data science mathematically interesting?
I have seen a plethora of job advertisements in the last few years on mathjobs.org for academic positions in data science. Now I understand why economic pressures would cause this to happen, but from ...
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
1answer
397 views
Large radical of an integer and three AB conjectures
In this Note, We propose a new definition called "large radical of an integer". Using this definition, three very useful $AB$ conjecture are given.
1. Large counter examples of the ABC conjecture
...
0
votes
1answer
60 views
Normal $0,1$-sequence with infinitely many frequent finite substrings
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
1
vote
0answers
71 views
Plethora of variant neural networks?
Since a decade ago when new life was breathed in to neural networks in the form of deep learning a plethora of different architectures have come about. Is there a reference that gives compendium of ...
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 ...
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 ...
4
votes
1answer
86 views
Is sum-balanceability computable?
Let $\mathbb{N}$ denote the set of positive integers, and let $G=(V,E)$ be a finite simple, undirected graph. Given $f:V\to \mathbb{Z}$ we define the neighborhood
sum function $\mathrm{nsum}_f:V\to\...
0
votes
0answers
68 views
Buridan's principle in computable analysis
In (Lamport, 2012), Lamport proposes the principle
A discrete decision based upon an input
having a continuous range of values cannot be made within a bounded length of time.
I think it could be ...
1
vote
0answers
42 views
Correctly defining a grah problem [closed]
I would like to solve a graph theory problem but I am struggling finding the most efficient Algo to solve it because I'm not correctly defining it. Here is my problem:
I have two sets of data:
A={A1,...
0
votes
0answers
41 views
Linear-algebraic simplification of the Smallest Grammar Problem
I don't get any people interested on MSE usually with this type of problem, and it is an untried idea. So I'm testing the waters out here. :)
The smallest grammar problem problem once solved will ...
4
votes
2answers
109 views
Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)
Currently, what conditions are known to be sufficient for the SDP relaxation of Max-Cut to be exact?
0
votes
3answers
369 views
Given $N$ integers on a circle, how to choose them in pairs to obtain minimum sum?
(Added by YCor 2019 July 7): it has been mentioned in the comments that this is part of a contest "Circular merging, July Challenge 2019 Division 1", where an equivalent question (just more clearly ...
3
votes
1answer
111 views
Computationally random bitstreams and normalcy
Let $\mathbb{N}$ denote the set of non-negative integers. We can identify every bitstream, i.e. a function $s:\mathbb{N}\to \{0,1\}$, with some $A\in{\cal P}(\mathbb{N})$: take $A = s^{-1}(\{1\})$.
...
0
votes
0answers
98 views
Are all cellular automata models related to the Bekenstein bound and the holographic principle?
Cellular automata are discrete models which have a regular finite dimensional grid of cells, each in one of a finite number of states, such as on and off.
There are various scientists that have ...
3
votes
1answer
137 views
$\sum_{i=1}^x\sum_{j=1}^xf(i\cdot j)$ Double Summing a (Not Completely) Multiplicative Function
Let $f(n)$ be a multiplicative function that is not completely multiplicative, i.e $f(m)\cdot f(n)= f(m\cdot n)$ only if $gcd(m,n)=1$. Let $S(x)$ be the double sum over $f$, that is:
$$S(x)=\sum_{i=1}...
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 ...
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 ...
3
votes
1answer
156 views
Some sums related to a quadratic polynomial over $\mathbb{F}_2^n$
For any $c \in \mathbb{F}_2^n$ define $\sigma_c: \mathbb{F}_2^n \to \mathbb{F}_2$ the quadratic polynomial defined for $v = (v_1,v_2,...,v_n)$ by:
$$ \sigma_c (v) = \sum_{i=1}^n v_iv_{i+1} + c_iv_i $...
5
votes
0answers
243 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, ...
7
votes
1answer
257 views
Coefficients of linear dependency
Let $L_1, \ldots, L_m \in \mathbb{Z}[x_1, \ldots, x_n]$ be polynomials of the form $L_i = l_{i1} \cdot l_{i2} \ldots \cdot l_{ik}$, where every $l_{ij}$ is an integer linear form.
Assume that ...
3
votes
1answer
145 views
What is known about this TSP variant?
Euclidian (planar) TSP asks for a tour with the minimum total length. The problem is known to be NP-hard. I am interested in the variant of finding a closed tour with the minimum enclosed area (...
7
votes
1answer
210 views
Logic with “co-relations” - sources?
My question is on a seemingly-natural extension of classical logic that I've been playing around with a bit in the context of generalized recursion theory. I'm sure it's been treated extensively ...
2
votes
1answer
90 views
Maximum number of $0$-$1$ vectors with a given rank
Let $k\ge2$. The maximum number of $0$-$1$ (column) vectors of length $2k-1$ which make a rank $k$ matrix with no zero row nor two identical rows is $2^{k-1}+1$. (The rank is over the rationals.)
I ...
5
votes
9answers
3k views
Applications of basic linear algebra concepts to computer science? [closed]
I'm trying to explain linear algebra to some programmers with computer science backgrounds. They took a course on it long ago, but don't seem to remember much. They can follow basic formalism, but ...
5
votes
2answers
235 views
Are there large integer matrices with entries computable in polynomial time, such that all minors are nonzero?
Is there a sequence of matrices $(A_n\in M_{2^n\times2^n}(\mathbb{Z}))_{n\in\mathbb{N}}$ such that the $(i,j)$th entry of $A_n$ is computable in polynomial time, such that all minors of each $A_n$ are ...
31
votes
11answers
2k views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
-1
votes
1answer
56 views
How to encode minimality constraint into SAT? [closed]
How to encode maximality/minimality constraints in SAT or its variants such as MaxSAT or MinSAT? For example, let us say (x1 OR x2) AND (x2 OR x3 OR x4) AND (x4 OR x5) is a formula. I want its ...
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 ...
3
votes
1answer
334 views
does recursive (decidable) languages closed under division (Quotient) with any language?
I need to prove or disprove that R languages are closed under divison.
I have managed to prove thet CFL are't closed under division. I read in wikipedia that RE languages are closed, but I didn't find ...
6
votes
1answer
97 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
3answers
860 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 ...
11
votes
1answer
542 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
67 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
9answers
887 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
86 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
51 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
60 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{ ...
52
votes
1answer
2k 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
160 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
134 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
93 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
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 ...
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:
...
