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.
622
questions
0
votes
1
answer
32
views
Isometric path cover number of the 2 dimensional grid graph
I am looking for a proof of the fact that at least $2n/3$ isometric paths (i.e. shortest paths between the end points) are required to cover the vertices of the $n\times n$ grid graph (i.e. Cartesian ...
11
votes
2
answers
1k
views
Soft question: Deep learning and higher categories
Recently, I have stumbled upon certain articles and lecture videos that use category theory to explain certain aspects of machine learning or deep learning (e.g. Cats for AI and the paper An enriched ...
1
vote
0
answers
59
views
A small lemma on cache resets (Bloom filters in particular)
Assume a fixed set of message $D$ and an associated distribution for selecting each message $d_i$ such that the total probability $\sum_{i \in D} d_i = 1$. We create a cache with $M$ bits and $k$ ...
1
vote
0
answers
80
views
Interpreting multiple property tests at different values of $\epsilon,\delta$ [closed]
I am doing some work in the area of Property Testing, as in Goldreich, Goldwasser, and Ron (2008) or the textbook Introduction to Property Testing (Goldreich). In this framework, I run a test to see ...
3
votes
0
answers
73
views
What does the computation of irrationality and transcendentality via a fancy implementation of analytic Markov's property look like?
Proofs that various real numbers are not rational or not algebraic tend to be constructively valid as is. Examples include the proofs that $\sqrt 2$ and $\log_2(3)$ are not rational and that $e$ is ...
1
vote
0
answers
51
views
Set functions satisfying if $f(X) \le f(Y)$ and $Z \cap (X \cup Y) = \emptyset$, then $f(X \cup Z) \le f(Y \cup Z)$
I am investigating set functions $f : 2^\Omega \to \mathbb{N}$ satisfying the following two properties:
(monotone) For all $X, Y \subset \Omega$, if $X \subseteq Y$, then $f(X) \le f(Y)$.
(property ...
1
vote
0
answers
100
views
When is a container a monad?
The category of polynomial functors on Set is equivalent to the category of containers.
We have a prescription for when a container is a comonad.
There are a few other questions that come to mind. ...
-5
votes
1
answer
69
views
Application of Resultant in Computer Algebra [closed]
Can you guys give me some application of resultant in Computer Algebra, it will be amazing if you guys can give me some paper or book to read more. Thanks so much
33
votes
3
answers
4k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
1
vote
0
answers
44
views
Computational complexity of exact computation of the doubling dimension
Given a finite metric space $X$, the doubling constant of $X$ is the smallest integer $k$ such that any ball of arbitrary radius $r$ can be covered by at most $k$ balls of radius $r/2$. The doubling ...
3
votes
1
answer
265
views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
0
votes
1
answer
54
views
Robustness of doubling dimension to small perturbations
Let $M$ be a metric space. Then the doubling dimension of $M$, denoted $\dim M$, is defined to be the minimum value $k$ such that every ball in $M$ of radius $r$ can be covered by at most $2^k$ balls ...
4
votes
0
answers
188
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
6
votes
1
answer
349
views
Large subgroups of Knuth's non-associative "group" on ${\cal P}(\mathbb{N})$
Donald Knuth introduced a fast, bit-wise approximation to integer addition by $$(a,b) \mapsto a \, ^{\land} \, b \, ^{\land} \, ((a \text{ & } b) \ll 1)$$
where $a,b$ are given in binary and $\,^{\...
56
votes
10
answers
7k
views
A clear map of mathematical approaches to Artificial Intelligence
I have recently become interested in Machine Learning and AI as a student of theoretical physics and mathematics, and have gone through some of the recommended resources dealing with statistical ...
2
votes
0
answers
176
views
Truncating the high degree part of a positive boolean function doesn't change the distance to positive functions too much
Given $\displaystyle n\in\mathbb{Z}^{+}$, suppose $\displaystyle f:\{-1,1\}^n\to[0,1], $ then $f$ has a Fourier expansion:
$\displaystyle f(x)=\sum_{S\subseteq[n]} \tilde{f}(S)x^S,$ where $\...
4
votes
2
answers
273
views
Approximating a fraction with a given denominator
Let $M$, $N$ be large natural numbers (say ~200 bits). Let $L$ be a smaller number, (say ~100 bits).
I want to approximate the fraction:
$$\frac{M}{N} \sim \frac{k}{L+r}$$
where $r$ is at most $L$. In ...
2
votes
0
answers
84
views
Constructing Hamiltonian circuits in acyclic digraphs
Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...
2
votes
1
answer
57
views
Left-shift cycle generating maps $f:\{0,1\}^{c_0}\to\{0,1\}$ for fixed length $c_0$
This is a strengthening of an older question.
Is there a positive integer $c_0$ with the following property?
For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that ...
43
votes
4
answers
4k
views
Lists as a foundation of mathematics
I am wondering if there is a foundation of mathematics where not sets or "set-like objects" (such as objects of a suitable topos as in ETCS) are the primitive notion, but rather lists. These ...
1
vote
0
answers
110
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
0
votes
0
answers
71
views
A problem on the factorizability of certain a boolean multivariate polynomial
Let $N$ be a positive integer and let $[N] := \{1,2,\ldots,N\}$. Given a non-empty collection $K$ of a subsets of $[N]$ and field $\mathbb F$, define a polynomial $f_K$ over $\{-1,+1\}$ in ...
4
votes
1
answer
461
views
How "correct" is Knuth's fast addition $(a,b) \mapsto (a \oplus b) \oplus ((a\land b) \ll 1)$?
Donald Knuth suggested a bitwise approximation for addition on the non-negative integers that is very fast on common processors:
$(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$,
where $a,b$ are ...
0
votes
0
answers
54
views
Given a set of time-series data, how would I determine another time-series is a linear combination of the set?
In other words, determine if sum linear combination of existing time-series could result in the desired time-series. I'm unsure if assumptions about the time-series may clarify the problem better, so ...
0
votes
0
answers
46
views
Approximation factor for TSP Algorithm
The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
0
votes
0
answers
47
views
Product types: algebraic structure for modeling product types with commutative and associative product operation
Is there a known algebraic structure over set of Types (however they are defined) which is equipped with:
commutative and associative product operation for building product types from simpler types, ...
1
vote
0
answers
104
views
Computing sine of gamma function [closed]
In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step?
Is there a ...
1
vote
1
answer
205
views
Rate of convergence to uniform distribution
Let $p=(p(1),\ldots,p(N))$ be a discrete distribution on $[N]:=\{1,2,\ldots,N\}$ with full support (i.e all the $p(i)$'s are strictly positive and sum to $1$). Let $i_1,i_2,\ldots,i_T$ be an iid ...
0
votes
1
answer
240
views
Is this kind of functor $\mathsf{Set}/M×\mathsf{Set}/M\to \mathsf{Set}/M$, with $M$ a monoid, a known construction?
I'm trying to construct lists with elements of type $A$ as the initial algebra over a base endofunctor in $\mathsf{Set}/\mathcal{P}(A)$, such that the list is indexed by the set of its elements.
My ...
1
vote
0
answers
95
views
Problems Correction of "Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "' [closed]
Where I can find the problems correction of this book " Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "
4
votes
1
answer
256
views
Discrepancy in the calculation of $2$-Selmer group by Magma and LMFDB
The result of LMFDB claims (https://www.lmfdb.org/EllipticCurve/Q/1640/c/1 )
that (2-part of) Tate-Shafarevich group $\mathrm{Sha}(E/\Bbb{Q})$ of elliptic curve $y^2=x^3-8747x-314874$ has order $16$. ...
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 ...
2
votes
0
answers
27
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 ...
5
votes
1
answer
750
views
Mathematics research relating to machine learning
What branch/branches of math are most relevant in enhancing machine learning (mostly in terms of practical use as opposed to theoretical/possible use)? Specifically, I want to know about math research ...
1
vote
1
answer
189
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 ...
4
votes
2
answers
242
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 \...
1
vote
1
answer
69
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 ...
0
votes
0
answers
65
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$ ...
2
votes
1
answer
65
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 ...
2
votes
0
answers
204
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 ...
1
vote
0
answers
83
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 ...
0
votes
0
answers
56
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
447
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. ...
35
votes
8
answers
3k
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
63
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
117
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 ...
1
vote
1
answer
527
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 ...
3
votes
0
answers
223
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 ...
3
votes
0
answers
101
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 ...
1
vote
0
answers
94
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$ ...