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

510
questions

**0**

votes

**0**answers

42 views

### Lower bounds on the length of circuits, depending on the number of times it crosses itself

I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...

**0**

votes

**1**answer

69 views

### Value (not position)- based sorting; reference request

A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation.
Many sort algorithms are position based: you ...

**3**

votes

**0**answers

178 views

### Can information be extracted more precisely using more random trials?

Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(y))$. What is the min of $n^{-1}H(x^n|f(y^n))$ over $f$ with $H(f(y^n))\leq nR$, taking $n\to \infty$?

**3**

votes

**1**answer

69 views

### What is known about computing all binary error correcting codes of given parameters?

Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$.
Are there any sources about using algorithms to find all given ...

**4**

votes

**3**answers

115 views

### Minimum number of swaps needed to 'group' a sequence?

Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...

**1**

vote

**0**answers

90 views

### Possible consequences in number theory and group theory if one-way functions exist explicitly? [closed]

It is known that the existence of one-way functions is an open and important problem in computer science. I read some of its implications, but it's still not clear at me what consequences we would ...

**4**

votes

**0**answers

60 views

### Amortized complexity of P

Let $P$ be the class of all polynomial time computable functions from $\{0,1\}^*\rightarrow \{0,1\}$. For any $f\in P$, define function $f^A:\mathbb{N}\rightarrow \{0,1\}^*$ by
$$f^A(n)=(f(x_1),\cdots,...

**-4**

votes

**1**answer

241 views

### PCP theorem to check hard proofs [closed]

Is it technically possible to check formidable proofs like Mochizuki's using PCP theorem before mathematicians spend time in understanding the mechanics of the proof? If so why have mathematicians not ...

**2**

votes

**0**answers

55 views

### Best known bound on feedback arcset in high-girth directed graphs?

Let $G$ be a directed graph with $n$ vertices and $m$ edges such that every directed cycle in $G$ has length at least $m/k$. An arcset of $G$ is defined as a set of edges $X$ whose removal from $G$ ...

**2**

votes

**0**answers

24 views

### Linear-time logspace encodable error correcting code with constant

Is there a binary code with (quasi)constant rate, constant relative distance, and an encoder that takes (quasi)linear time and logspace simultaneously? Note that there are no constraints on ...

**4**

votes

**0**answers

199 views

### A conjecture about the barycenter of a polytope

Could someone help me with the following conjecture? Thanks a lot!
Suppose I have a polytope $\Delta$ in $\mathbb R^n (n\geq 2)$ with coordinates $(x_1,x_2,\cdots,x_n)$ defined by linear ...

**2**

votes

**1**answer

263 views

### Having a paper published via both Conference Proceedings and via a refereed journal

Forgive me if this isn't the right place to pose this question. I do need guidance on this.
In 2018 I had submitted a paper to a refereed journal. It had gotten accepted for publication by said ...

**2**

votes

**0**answers

64 views

### Iterated removal of singleton Pythagorean triples

Consider the set of all Pythagorean triples (positive integers $a, b, c$ such that $a^2 + b^2 = c^2$, not necessarily coprime). Then for each integer that appears in exactly one triple, remove that ...

**1**

vote

**1**answer

124 views

### Gröbner basis via integer programming

I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...

**2**

votes

**1**answer

88 views

### Can quantum codes have more than $c \cdot \sqrt{N}$ correction distance for N encoding qbits?

I'm not an expert in quantum computing at all, but recently I've started to learn it (read Shen-Vyalyi-Kitaev's book and looked up some other literature here and there).
There are few remarkable ...

**27**

votes

**7**answers

4k views

### Decision problems for which it is unknown whether they are decidable

In computability theory, what are examples of decision problems of which it is not known whether they are decidable?

**0**

votes

**0**answers

122 views

### A matching like problem

Consider finite sets S and R and a symmetric function $f:S\times S\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 ...

**0**

votes

**1**answer

145 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

**1**answer

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

**69**

votes

**6**answers

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

**1**answer

171 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 $\...

**5**

votes

**1**answer

433 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

**1**answer

67 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

**0**answers

80 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

**0**answers

116 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

**0**answers

123 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

**1**answer

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

**1**

vote

**0**answers

72 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

**0**answers

45 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

**0**answers

62 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

**2**answers

138 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

**3**answers

420 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

**1**answer

121 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

117 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

**1**answer

144 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

**0**answers

44 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

**0**answers

322 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

**1**answer

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

**4**

votes

**0**answers

258 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

**1**answer

262 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

156 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

223 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

**1**answer

94 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

**9**answers

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

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

**32**

votes

**11**answers

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

**1**answer

60 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

**0**answers

217 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

**1**answer

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

**7**

votes

**1**answer

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