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.
653 questions
41
votes
12
answers
8k
views
Examples for the use of AI and especially LLMs in notable mathematical developments
The purpose of this question is to collect examples where large language models (LLMs) like ChatGPT have led to notable mathematical developments.
The emphasis in this question is on LLMs, but ...
6
votes
2
answers
779
views
Which conjectures have been solved (or partially solved) using entropy methods?
I am studying how entropy-based arguments (in the sense of Shannon, Boltzmann, or Perelman's geometric entropy) can be used to prove or guide the resolution of major mathematical conjectures.
Some ...
3
votes
1
answer
198
views
Supernormal sequences
We call a binary sequence $s:\mathbb{N}\to\{0,1\}$ supernormal if
for every injective, increasing and computable function $\iota:\mathbb{N}\to\mathbb{N}$, the binary sequence $s\circ\iota:\mathbb{N}\...
11
votes
1
answer
461
views
Is there any algorithm which can find a common divisor of two polynomials modulo $p^k$?
Let us consider two monic polynomials $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$. Now, we call $h(X)$ is a divisor of $f(X)$, if there exists a $l(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]...
- 311
0
votes
0
answers
167
views
Algorithms for searching equal sums of like powers (taxicab problem)
I am developing a brute-force algorithm to search for solutions to the generalized taxicab equation, $a^k + b^k = c^k + d^k$ between a lower and upper bound. My current approach is a priority queue-...
8
votes
0
answers
654
views
Automating the resolution of IMO 2025 Problem 1
The problem 1 of the 2025 IMO is the following:
A line in the plane is called sunny if it is not parallel to any of the x-axis, the y-axis, and the line $x + y = 0$.
Let $n ⩾ 3$ be a given integer.
...
- 371
1
vote
0
answers
109
views
Is the NH hash family $\varepsilon$-AXU?
As context, I'll start with summarizing and simplifying the section of "UMAC: Fast and Secure Message Authentication", by Black et al.(https://www.cs.ucdavis.edu/~rogaway/papers/umac-full....
- 111
2
votes
1
answer
177
views
Gröbner Basis That do not Introduce New Indeterminates
Let $\vec{X}$ be a finite set of indeterminates, and $\sqsubseteq$ be a monomial ordering.
A Gröbner Basis $B$ of an ideal $I$ of polynomials can be characterized as a finite set of polynomials ...
20
votes
4
answers
2k
views
Is there a concept of Turing Machine over a group, not just over the integers as a model of the tape?
For a Turing machine with an infinite tape, the tape may be modeled by the group of integers. So a rule $(q,a,b,m,r)$ says "in state $g$ if see $a$ on tape replace it by $b$ and go left if $m=-1$ ...
- 521
15
votes
2
answers
1k
views
What is the implicit pseudorandomness conjecture behind the use of e.g. numpy.random() for probabilistic applications?
Suppose I want to investigate some complicated probabilistic phenomenon numerically, e.g. the eigenvalues of random matrices. One thing I might do is (ask some software to) generate a bunch of random ...
- 124k
6
votes
1
answer
290
views
Deciding positivity for polynomials summed across a regular language
Motivation: Long story short, this problem arose after a number of reductions and simplifications from a question in symbolic dynamics motivated by the paper Symbolic discrepancy and self-similar ...
- 1,483
7
votes
1
answer
252
views
Polynomially normal binary sequences
Motivation. When we try to construct a (pseudo-)random sequence $s:\newcommand{\N}{\mathbb{N}}\N\to\{0,1\}$ we often want $s$ itself, and some of its subsequences, to be normal.
Question. Is there a ...
1
vote
1
answer
114
views
Surjective hash functions $h:\{0,1\}^* \to \{0,1\}^{2n}$ with avalanche effect
Motivation. In computer science, hash functions are maps that convert binary strings of arbitrary length to a fixed-length binary string. In symbols, we have a map $h:\{0,1\}^* \to \{0,1\}^n$ for some ...
1
vote
1
answer
135
views
Graph classes which have small edge k-cuts
I am interested in graph classes that have the following property: There exists a function $f(k)$ such that for every graph $G$ in the class, for every choice of $k$ vertices $v_1, \ldots, v_k$ in the ...
- 528
5
votes
2
answers
2k
views
Shifting an irrational binary sequence
Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be ...