Skip to main content

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
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), ...
user528933's user avatar
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 ...
Andi Bauer's user avatar
  • 2,911
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 ...
Dmitri Scheglov's user avatar
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 ...
Paul Calvi 's user avatar
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 ...
Agile_Eagle's user avatar
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 ...
en-drix's user avatar
  • 93
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 $...
ABB's user avatar
  • 4,010
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 ...
Dominic van der Zypen's user avatar
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 ...
Pritam Majumder's user avatar
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 ...
h3fr43nd's user avatar
  • 231
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$ ...
Birdy Nam Nam's user avatar
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 ...
Paul's user avatar
  • 171
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 ...
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
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. ...
Ben Sprott's user avatar
  • 1,349
-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
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
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 ...
pyridoxal_trigeminus's user avatar
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 ...
poeaqnwgo's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
poeaqnwgo's user avatar
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 $\,^{\...
Dominic van der Zypen's user avatar
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 $\...
qmww987's user avatar
  • 49
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 ...
mtheorylord's user avatar
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 ...
ABB's user avatar
  • 4,010
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
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''...
truebaran's user avatar
  • 9,210
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 ...
dohmatob's user avatar
  • 6,764
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 ...
Dominic van der Zypen's user avatar
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 ...
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
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, ...
000 000's user avatar
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 ...
roignoirewg's user avatar
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 ...
dohmatob's user avatar
  • 6,764
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
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 "
zdo0x0's user avatar
  • 11
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$. ...
Duality's user avatar
  • 1,457
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.7k
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 ...
Ilovemath's user avatar
  • 625
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 ...
Artus's user avatar
  • 173
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 ...
dohmatob's user avatar
  • 6,764
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 \...
dohmatob's user avatar
  • 6,764
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 ...
Sidharth Ghoshal's user avatar
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 ...
Alec Jacobson's user avatar
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 ...
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
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. ...
Duncan W's user avatar
  • 341

1
2 3 4 5
13