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.

Filter by
Sorted by
Tagged with
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 ...
Pritam Majumder's user avatar
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 ...
h3fr43nd's user avatar
  • 221
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$ ...
Birdy Nam Nam's user avatar
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 ...
Paul's user avatar
  • 171
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 ...
Christopher King's user avatar
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 ...
Glenn Sun's user avatar
  • 151
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. ...
Ben Sprott's user avatar
  • 1,281
-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
Luật Trần Văn's user avatar
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....
schnitzi's user avatar
  • 463
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 ...
pyridoxal_trigeminus's user avatar
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 ...
poeaqnwgo's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
poeaqnwgo's user avatar
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 $\,^{\...
Dominic van der Zypen's user avatar
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 $\...
qmww987's user avatar
  • 49
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 ...
mtheorylord's user avatar
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 ...
ABB's user avatar
  • 3,898
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 ...
Dominic van der Zypen's user avatar
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 ...
Martin Brandenburg's user avatar
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''...
truebaran's user avatar
  • 9,140
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 ...
dohmatob's user avatar
  • 6,706
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 ...
Dominic van der Zypen's user avatar
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 ...
Kevin Jiang's user avatar
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 ...
Mathematician....'s user avatar
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, ...
000 000's user avatar
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 ...
roignoirewg's user avatar
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 ...
dohmatob's user avatar
  • 6,706
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 ...
cxandru's user avatar
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 "
zdo0x0's user avatar
  • 11
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$. ...
Duality's user avatar
  • 1,407
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 ...
Turbo's user avatar
  • 13.6k
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 ...
Ilovemath's user avatar
  • 585
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 ...
Artus's user avatar
  • 173
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 ...
dohmatob's user avatar
  • 6,706
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 \...
dohmatob's user avatar
  • 6,706
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 ...
Sidharth Ghoshal's user avatar
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$ ...
Dominic van der Zypen's user avatar
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 ...
Alec Jacobson's user avatar
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 ...
borekking's user avatar
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 ...
koch's user avatar
  • 21
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 ...
user499408's user avatar
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. ...
Duncan W's user avatar
  • 341
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 ...
Drinkwater_84's user avatar
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 ...
Marco Ripà's user avatar
  • 1,102
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 ...
Marco Ripà's user avatar
  • 1,102
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 ...
mathematrucker's user avatar
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 ...
Dominic van der Zypen's user avatar
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$ ...
Gerrit Begher's user avatar

1
2 3 4 5
13