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.
590
questions
11
votes
1
answer
1k
views
Smale's view of mathematical artificial intelligence
This snippet is from Smale's paper Smale, Steve (1999). "Mathematical problems for the next century". In Arnold, V. I.; Atiyah, M.; Lax, P.; Mazur, B. (eds.). Mathematics: frontiers and ...
- 13.4k
1
vote
0
answers
17
views
Free programs suggestions to simulate parabolic EDPs
I'm interested in learning how to computationally simulate the behavior of parabolic partial differential equations, but I don't know where to start, what are the best free programs to use and where ...
- 337
0
votes
1
answer
160
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 6,338
4
votes
2
answers
213
views
Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
- 6,338
1
vote
1
answer
53
views
Where to find hard instances of subsetsum and other famous np-complete problems for testing heuristics against?
[Can move to cs or tcs stackexchange if thats a better home]
I remember back around 2016 DIMACS used to host a list of problem instances of various famous problems in the NP-complete class and harder ...
- 1,450
0
votes
0
answers
62
views
Pseudo-isomorphicity as a polynomial-time fingerprint for graphs
Motivation. It is well-known that determining whether two graphs $G_1, G_2$ on $n$ vertices are isomorphic, is hard. The iterated degree matrix $\mathbb{D}(G)$ of a finite simple undirected graph $G$ ...
- 42.6k
2
votes
1
answer
44
views
Example of worst case distributions for 4D convex hull
My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf
This same source writes
In 4D, there are ...
- 673
2
votes
0
answers
157
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
1
vote
0
answers
75
views
Convex optimization with one-point feedback
In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify ...
- 21
0
votes
0
answers
51
views
NC0 randomness vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
4
votes
4
answers
423
views
Automatically generating combinatorial conjectures
It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
- 341
33
votes
8
answers
2k
views
Examples of errors in computational combinatorics results
I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
1
vote
0
answers
59
views
Does Frobenius number increase if bound on input increases?
The Frobenius number F is the largest number not expressible as a non-negative linear combination of some set of positive integers $\{a_i\}$, where, $a_i$ has gcd 1. Denote $maxF(n)$ as the maximum of ...
0
votes
0
answers
112
views
Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point
In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...
- 648
1
vote
1
answer
442
views
Finding an optimal covering trail for the set $\{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\}$
Here is a key question (i.e., Question 2 below) that, if correctly answered, would let me support a very general conjecture on a wide class of related problems, a conjecture that I have never shared ...
- 648
3
votes
0
answers
209
views
How rigorously can we apply the data supplied by this nonstandard attack on Kuratowski's closure-complement problem?
Suppose a student assigned an advanced version of Kuratowski’s closure-complement problem to solve—one that leaves out the standard hint about the finite upper bound of $14$—decides to look for the ...
- 808
3
votes
0
answers
89
views
Hamiltonian path in $\{0,1\}^n$ with rotations and bit-flip in position 0
We consider any non-negative integer as an ordinal, that is $0=\emptyset$ and $n=\{0,\ldots,n-1\}$ for every positive integer. Let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$.
Define ...
- 42.6k
1
vote
0
answers
91
views
Reference request: Time and proofs of shared pasts
Is there research about structures for notions of time with distributed systems of information, as with blockchains?
I am thinking of tuples $(I, T, P, A, \prec, s, \eta, u)$ where
$I$, $T$ and $P$ ...
- 3,103
7
votes
1
answer
344
views
About the complexity of some operation involving integers
There are two integers: $A, B$. Given the below four allowed operations (and only them):
$A+1$, $A-1$, $\sqrt{A}$, $A^2$
Also, it is only allowed to take the square root of $A$ when this square root ...
- 71
11
votes
3
answers
690
views
Can computers find zeros of order $2$?
We assume we are given an entire function $f: \mathbb C \to \mathbb C$ with $f(0)=1$ and $f'(0)=0$ and $f$ is real on the real axis.
We assume (as a fact about $f$, that we want to demonstrate ...
- 624
0
votes
1
answer
88
views
Non-isomorphic graphs with identical iterated degree matrix
If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$
Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \...
- 42.6k
2
votes
1
answer
126
views
Union of admissible words are subshift of finite type
Assume that $Q=(q_{ij})$ is a $k\times k$ with $q_{ij}\in \{0, 1\}.$ The two side subshift of finite type associated to the matrix $Q$ is a left shift map $T:\Sigma_{Q}\rightarrow \Sigma_{Q}$, where
...
- 929
4
votes
0
answers
78
views
$\omega$ incompleteness of $\lambda$ calculus
In Plotkin's 'The $\lambda$-Calculus is $\omega$-Incomplete' (The Journal of Symbolic Logic Vol. 39, No. 2 (Jun., 1974), pp. 313-317), an example is given of two (untyped) $\lambda$-terms $M$ and $N$ ...
- 304
4
votes
1
answer
295
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 1,109
0
votes
0
answers
66
views
3D interpolation function
I've got a 3D figure created using around 30k points and has different regions colored in an specific way according to some unrelated variables that come from a project I'm creating. Taking in ...
8
votes
1
answer
372
views
Smallest relation in complement of partial order that prohibits its extension
Let $P$ be a partial order on a finite set $S$ (assume that every element is related to at least one other element besides itself…this raises a few quick questions: is this implied by the definition ...
- 808
4
votes
1
answer
243
views
Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?
This question is a follow-up of this question.
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd.
Question: Can we compute the exact minimum $$A:=
\min_{u:\mathbb{...
- 6,499
9
votes
1
answer
377
views
Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?
Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let
$u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd.
Is it possible that
$$
\sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
- 6,499
4
votes
2
answers
180
views
Hamilton cycles in $\{0,1\}^n$ with fixed Hamming distance
Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge ...
- 42.6k
1
vote
1
answer
67
views
Cycling through $\{0,1\}^n$ by shifting and applying a $n$-ary function
This question is motivated by Linear Feedback Shift Registers, which cycle through $\{0,1\}^n \setminus \{(0,\ldots,0)\}$ by shifting and applying a small set of XOR operations.
Let $n>1$ be an ...
- 42.6k
5
votes
1
answer
211
views
Cycling through $\{0,1\}^{(2^n)}$ such that all Hamming distance appear equally frequently
Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$....
- 42.6k
3
votes
1
answer
200
views
Is normalcy preserved under the swapping operation?
Let $\mathbb{N}$ denote the set of non-negative integers. We say that a sequence $f:\mathbb{N}\to \{0,1\}$ is normal if every finite $\{0,1\}$-sequence appears in $f$.
Let the swapping operation $\...
- 42.6k
2
votes
0
answers
135
views
Binary operation approximating "addition" on $2^\omega$
Motivation. In computer science, addition of integers $a+b$ can be approximated by a very fast operation: $(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$, where $\oplus$ denotes bitwise XOR, $\...
- 42.6k
1
vote
1
answer
153
views
Boolean function : approximation by a linear function
Let $f$ be a balanced Boolean function.
Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$
$g ...
- 3,365
1
vote
1
answer
78
views
Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof
I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010 [1], which, roughly, states that there is a many-one reduction ...
- 11
2
votes
0
answers
98
views
When does Le Cam's method give tight lower bounds for distribution testing?
In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: ...
- 33
2
votes
1
answer
92
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
- 6,338
0
votes
1
answer
263
views
Can finite sets be non-c.e. depending on how they are presented?
I ask the question because of the following statement found in Mark Burgin's paper, "Algorithmic complexity of recursive and inductive algorithms", Theoretical Computer Science 317 (2004) 31-...
- 5,926
-1
votes
1
answer
81
views
Finding a $k$-subset which maximizes a matrix sum
Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:
Is there a polynomial-time solution to the following ...
1
vote
1
answer
135
views
Is Toom's rule robust under local but non-on-site noise?
Toom's rule is a 2-dimensional cellular automaton which is known to have two distinct stationary measures in the thermodynamic limit, even after small perturbations to a probabilistic cellular ...
- 2,769
3
votes
0
answers
94
views
Are there (probablistic) uniform 1D cellular automata which can fault-tolerantly store one bit?
In two dimensions, "Toom's rule" is known to be a cellular automaton which can fault-tolerantly store one bit of information. This means that, if we start with the all-0 configuration on an $...
- 2,769
3
votes
1
answer
144
views
Is factorial computation known to be in a class smaller than $FEXP$?
Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
- 13.4k
0
votes
0
answers
94
views
Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace
Let $q$ be a fixed prime, $P, Q$ be polynomials with $\mathrm{deg}(Q) < \mathrm{deg}(P)$ and $h = O(\log n)$.
Let $S$ be a subset of $\mathbb{F}_q^n$ of size $P(n)$ such that there exists a subset ...
- 328
5
votes
1
answer
284
views
Why is this nonlinear transformation of an RKHS also an RKHS?
I came across this paper (beginning of page 6) where they stated that if $f,h\in \mathcal{H}$, where $\mathcal{H}$ is an RKHS, then $l_{h,f}=\left|f(x)-h(x)\right|^q$ where $q\geq 1$ also belongs to ...
- 343
0
votes
1
answer
848
views
How does the greedy algorithm for CSES problem collecting numbers work? [closed]
The collecting numbers problem in the CSES problem set has a greedy solution where we compare the position of a number x with the position of x-1. If pos(x) < pos(x-1) then we increment rounds ...
- 101
2
votes
0
answers
175
views
Are there some algorithms which have high consistency strength?
Are there some algorithms, their time complexity is relatively good, for example polynomial time.
And the correctness of them has high consistency strength.
And these algorithms shouldn't able to ...
- 1,056
8
votes
1
answer
410
views
Does the morphism of composition have some universal property?
Let $A$, $B$ and $C$ be three objects in the category Set. For simplicity, assume that their underlying sets contain a finite number of elements, a, b and c respectively. Using the usual Haskell ...
16
votes
6
answers
5k
views
Revisiting the unreasonable effectiveness of mathematics
Question:
On balance, with theoretical advances in algorithmic information theory and Quantum Computation it appears that the remarkable effectiveness of mathematics in the natural sciences is quite ...
- 3,639
5
votes
1
answer
183
views
Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$
Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b "=...
- 42.6k
1
vote
1
answer
349
views
Cramer–Castillon problem like
Special case of Golden ratio as a property of conic section (is it known?) as follows:
Let $ABC$ be arbitrary triangle and $DEF$ is the its tangential triangle. Let $CF$ meets $AB$ at $G$ and $BE$ ...
- 1,014