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

479
questions

**0**

votes

**0**answers

20 views

### Ranking system with inverse points calculation system [on hold]

I'm trying to solve a calculation problem for an algorithm which aims to achieve the following:
Each company is ranked every year;
The rankings go from 1 (first or 'best') to n (as usual);
I started ...

**4**

votes

**2**answers

91 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?

**3**

votes

**0**answers

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

**3**

votes

**1**answer

106 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

**0**answers

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

**74**

votes

**3**answers

3k views

### How feasible is it to prove Kazhdan's property (T) by a computer?

Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually ...

**3**

votes

**1**answer

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

**28**

votes

**16**answers

11k views

### Programming Languages Based on Category Theory

Since some computer scientists use category theory, I was wondering if there are any programming languages that use it extensively.

**3**

votes

**0**answers

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

**19**

votes

**3**answers

894 views

### Which distributions can you sample if you can sample a Gaussian?

Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...

**7**

votes

**0**answers

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

**5**

votes

**0**answers

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

**3**

votes

**1**answer

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

**7**

votes

**1**answer

254 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

**1**answer

130 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

**1**answer

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

**4**

votes

**3**answers

2k views

### Optimal packing of spheres tangent to a central sphere

Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$.
My question concerns optimal values for the ...

**30**

votes

**11**answers

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

**2**

votes

**1**answer

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

**-1**

votes

**1**answer

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

**11**

votes

**1**answer

591 views

### I am searching for the name of a partition (if it already exists)

I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a ...

**5**

votes

**9**answers

2k 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

**2**answers

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

**6**

votes

**3**answers

589 views

### On the inequality $\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq c\left(\sum_{i=1}^nx_i^3\right)^2$

I'm have some difficulties in bounding the following inequality:
I want to find a c as small as possible s.t.
$$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq c\left(\sum_{i=1}^nx_i^3\...

**19**

votes

**3**answers

927 views

### Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:
Find a decision procedure for determining if an arbitrary semilinear set
is a ...

**7**

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

**13**

votes

**0**answers

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

**15**

votes

**9**answers

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

**14**

votes

**1**answer

1k views

### Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...

**3**

votes

**1**answer

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

**17**

votes

**1**answer

1k views

### Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...

**6**

votes

**1**answer

94 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

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

**39**

votes

**17**answers

11k views

### Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scientists post questions looking to learn things ...

**11**

votes

**1**answer

533 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

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

**2**

votes

**1**answer

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

**15**

votes

**1**answer

482 views

### Constructive Mathematics and Termination

In the 1988 book The Universal Turing Machine A Half-Century Survey
there is the paper "The Confluence of Ideas in 1936" by Robin Gandy. In section 4.2, Gandy writes:
"If one accepts, on whatever ...

**2**

votes

**1**answer

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

**11**

votes

**2**answers

399 views

### Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...

**40**

votes

**1**answer

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

**2**

votes

**0**answers

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

**3**

votes

**1**answer

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

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

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

**2**

votes

**1**answer

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

**6**

votes

**0**answers

1k views

### Hash functions and inner product

As part of a research project on derandomization of linear threshold functions I am working on, I am trying to understand the following problem:
Is there a small (polynomial rather than exponential)...

**6**

votes

**0**answers

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

**23**

votes

**3**answers

1k views

### Expected edit distance

The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{...

**3**

votes

**0**answers

380 views

### Inversion density: Have you seen this concept?

Let $n > 1$ be an integer.
Let $A$ be an array, indexed from $1$ to $n$, of $n$ values
$A(i)$ coming from the finite set $\{0,1\}$.
(More generally, the values can come from any
totally ordered ...