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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
125 views

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 ...
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,...
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 ...
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?
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 ...
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\})$. ...
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 ...
137 views

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