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.
641 questions
7
votes
3
answers
835
views
Error correcting codes - basic question
Hi,
I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...
CommunityBot
- 1
4
votes
0
answers
76
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,...
- 509
-3
votes
1
answer
479
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 ...
- 1,826
11
votes
2
answers
950
views
Define Turing machine with algebraic concepts/structures
Usually, during lectures Turing Machines are firstly introduced from an informal point of view (for example, in this way) and then their definition is formalized (for example, in this way).
Is it ...
- 63.9k
2
votes
0
answers
109
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$ ...
10
votes
4
answers
1k
views
Complete extensions of first order logic (or language)
Lindstrom's theorem states that any extension of first order logic (FOL) more expressible than FOL fails to have either compactness or Lowenheim-Skolem. When I first read Lindstrom's theorem my first ...
- 63.9k
2
votes
0
answers
70
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 ...
- 479
43
votes
10
answers
7k
views
What is the shortest program for which halting is unknown?
In short, my question is:
What is the shortest computer program for which it is not known whether or not the program halts?
Of course, this depends on the description language; I also have the ...
- 1,734
4
votes
0
answers
287
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 ...
- 4,713
3
votes
1
answer
334
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 ...
- 91.8k
2
votes
0
answers
77
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 ...
- 130
20
votes
2
answers
2k
views
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
CommunityBot
- 1
1
vote
1
answer
237
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
120
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 ...
- 238
0
votes
0
answers
127
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 ...
- 10.4k
5
votes
1
answer
306
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 ...
- 14.2k
0
votes
1
answer
210
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 ...
- 6,969
11
votes
3
answers
8k
views
How to calculate the sum of remainders of N?
I'm trying to sum the remainders when dividing N by numbers from $1$ up to $N$
$$\sum_{i = 1}^{N} N \bmod i$$
It's easy to write a program to evaluate the sum if N is small in $O(N)$ but what if N is ...
- 441
4
votes
1
answer
498
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
...
- 1,384
0
votes
1
answer
81
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\})$.
...
- 11.4k
1
vote
0
answers
107
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 ...
- 13.9k
30
votes
1
answer
592
views
Guess that group via product queries
Suppose someone (person B) knows a finite group $G$ of order $n$.
You (person A) know only the order $n$,
and that $1$ is the name of the identity element.
The group elements are named $1,2,\ldots,n$ ...
- 13.9k
3
votes
0
answers
155
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 ...
CommunityBot
- 1
4
votes
1
answer
160
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\...
- 32.1k
2
votes
0
answers
149
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 ...
- 3,486
2
votes
0
answers
103
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 ...
0
votes
3
answers
1k
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 ...
- 13k
5
votes
2
answers
633
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
95
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)$ ...
2
votes
1
answer
152
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\})$.
...
- 54.2k
4
votes
1
answer
375
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}...
- 12.8k
3
votes
0
answers
59
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 ...
- 1,080
19
votes
3
answers
1k
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 ...
- 6,045
9
votes
0
answers
2k
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 ...
- 82.7k
4
votes
0
answers
274
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, ...
- 13k
3
votes
1
answer
183
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 $...
- 1,101
7
votes
1
answer
285
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 ...
- 156k
3
votes
1
answer
262
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 (...
8
votes
1
answer
301
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 ...
- 48.8k
5
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 ...
- 4,713
2
votes
1
answer
102
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 ...
- 6,101
-1
votes
1
answer
89
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 ...
- 63.9k
11
votes
1
answer
696
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 ...
- 32.5k
5
votes
9
answers
7k
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 ...
- 12.6k
5
votes
2
answers
285
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 ...
- 558
7
votes
3
answers
709
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\...
- 63.9k
19
votes
3
answers
1k
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 ...
- 245
10
votes
0
answers
4k
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:
$...
CommunityBot
- 1
13
votes
0
answers
257
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 ...
- 48.9k
16
votes
9
answers
1k
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 ...
