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

629
questions

0
votes

0
answers

86
views

### How can I transform every graph into one with constant out-degree?

I am working on my master thesis and try to implement a new shortest path algorithm from the following paper: https://arxiv.org/abs/2203.03456
In some of the functions (for example ScaleDown), ...

1
vote

1
answer

69
views

### Probabilistic 2D cellular automata with memory lifetime increasing like $e^{L^2}$

Consider 2-state probabilistic cellular automata on an $L\times L$ torus square lattice which has the all-$0$ and all-$1$ configurations as fixed points, thinking of something similar to Toom's rule ...

4
votes

1
answer

269
views

### rank of an integer valued matrix

I make some numerical experiments, involving rank of integer valued matrices of the size about $14\times 24$. As the matrix is integer valued, theoretically there should be no room for errors. However ...

2
votes

0
answers

168
views

### NP-hardness of a string transformation problem with k templates

Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...

2
votes

0
answers

38
views

### graphs which have polynomial bounded number of cycles

How does the graph class defined as those graphs which have polynomial (or quasi polynomial) bounded number of cycles look? (in number of vertices)
I suspect it will rather non-interesting as ...

8
votes

1
answer

2k
views

### Polynomial-time quantum algorithms for lattice problems (GapSVP, SIVP, LWE)

The author of a recent preprint claims to have found polynomial-time quantum algorithms for solving the following lattice problems: the Decisional Shortest Vector Problem (GapSVP), the Shortest ...

1
vote

2
answers

185
views

### Topology of directed graph $G$ with non-singular adjacency matrix

Given a directed graph $G$ with non-singular adjacency matrix,
Q. Is there a directed
subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...

1
vote

1
answer

157
views

### Permutation graph with insert-and-shift

Motivation. I am working with a database software that allows
you to sort the fields of any given table in the following
peculiar way. Suppose your fields are numbered $1,\ldots, 18$.
Next to every ...

0
votes

2
answers

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

12
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

60
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

81
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

85
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

110
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

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

2
votes

0
answers

57
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

284
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

60
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

196
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

352
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

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

185
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

296
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

94
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

112
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

72
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

470
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

58
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

55
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

108
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

249
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

97
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

270
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

28
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

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

190
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

263
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

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

2
votes

1
answer

72
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

221
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

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