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
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.4k
1 vote
0 answers
17 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
  • 337
0 votes
1 answer
160 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,338
4 votes
2 answers
213 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,338
1 vote
1 answer
53 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
62 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
44 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
157 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
75 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
51 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
423 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
33 votes
8 answers
2k 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
59 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
112 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 vote
1 answer
442 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
3 votes
0 answers
209 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
89 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
91 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
7 votes
1 answer
344 views

About the complexity of some operation involving integers

There are two integers: $A, B$. Given the below four allowed operations (and only them): $A+1$, $A-1$, $\sqrt{A}$, $A^2$ Also, it is only allowed to take the square root of $A$ when this square root ...
crosscc's user avatar
  • 71
11 votes
3 answers
690 views

Can computers find zeros of order $2$?

We assume we are given an entire function $f: \mathbb C \to \mathbb C$ with $f(0)=1$ and $f'(0)=0$ and $f$ is real on the real axis. We assume (as a fact about $f$, that we want to demonstrate ...
Pritam Bemis's user avatar
0 votes
1 answer
88 views

Non-isomorphic graphs with identical iterated degree matrix

If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$ Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \...
Dominic van der Zypen's user avatar
2 votes
1 answer
126 views

Union of admissible words are subshift of finite type

Assume that $Q=(q_{ij})$ is a $k\times k$ with $q_{ij}\in \{0, 1\}.$ The two side subshift of finite type associated to the matrix $Q$ is a left shift map $T:\Sigma_{Q}\rightarrow \Sigma_{Q}$, where ...
Adam's user avatar
  • 929
4 votes
0 answers
78 views

$\omega$ incompleteness of $\lambda$ calculus

In Plotkin's 'The $\lambda$-Calculus is $\omega$-Incomplete' (The Journal of Symbolic Logic Vol. 39, No. 2 (Jun., 1974), pp. 313-317), an example is given of two (untyped) $\lambda$-terms $M$ and $N$ ...
provocateur's user avatar
4 votes
1 answer
295 views

Lower bound on the number of solutions of 2SAT

To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
Alberto Montina's user avatar
0 votes
0 answers
66 views

3D interpolation function

I've got a 3D figure created using around 30k points and has different regions colored in an specific way according to some unrelated variables that come from a project I'm creating. Taking in ...
Vako Galvan's user avatar
8 votes
1 answer
372 views

Smallest relation in complement of partial order that prohibits its extension

Let $P$ be a partial order on a finite set $S$ (assume that every element is related to at least one other element besides itself…this raises a few quick questions: is this implied by the definition ...
mathematrucker's user avatar
4 votes
1 answer
243 views

Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?

This question is a follow-up of this question. Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and suppose that $n$ is odd. Question: Can we compute the exact minimum $$A:= \min_{u:\mathbb{...
Asaf Shachar's user avatar
  • 6,499
9 votes
1 answer
377 views

Are there functions $\mathbb{F}_2^n \to \mathbb{F}_2$ satisfying these special relations?

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements, and let $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$. Suppose that $n$ is odd. Is it possible that $$ \sum_{x \in \mathbb{F}_2^n}(-1)^{u(x)+u(...
Asaf Shachar's user avatar
  • 6,499
4 votes
2 answers
180 views

Hamilton cycles in $\{0,1\}^n$ with fixed Hamming distance

Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge ...
Dominic van der Zypen's user avatar
1 vote
1 answer
67 views

Cycling through $\{0,1\}^n$ by shifting and applying a $n$-ary function

This question is motivated by Linear Feedback Shift Registers, which cycle through $\{0,1\}^n \setminus \{(0,\ldots,0)\}$ by shifting and applying a small set of XOR operations. Let $n>1$ be an ...
Dominic van der Zypen's user avatar
5 votes
1 answer
211 views

Cycling through $\{0,1\}^{(2^n)}$ such that all Hamming distance appear equally frequently

Let $n\in\mathbb{N}$ be a positive integer. Let $\{0,1\}^{(2^n)}$ be the set of $0,1$-sequences of length $2^n$. For $a,b\in \{0,1\}^{(2^n)}$ let $d_h(a,b)$ be the Hamming distance between $a$ and $b$....
Dominic van der Zypen's user avatar
3 votes
1 answer
200 views

Is normalcy preserved under the swapping operation?

Let $\mathbb{N}$ denote the set of non-negative integers. We say that a sequence $f:\mathbb{N}\to \{0,1\}$ is normal if every finite $\{0,1\}$-sequence appears in $f$. Let the swapping operation $\...
Dominic van der Zypen's user avatar
2 votes
0 answers
135 views

Binary operation approximating "addition" on $2^\omega$

Motivation. In computer science, addition of integers $a+b$ can be approximated by a very fast operation: $(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$, where $\oplus$ denotes bitwise XOR, $\...
Dominic van der Zypen's user avatar
1 vote
1 answer
153 views

Boolean function : approximation by a linear function

Let $f$ be a balanced Boolean function. Are there $g$ linear functions, with $$\frac1{2^n}\mathrm{card} \big(\big\{\mathrm{sign} (g (x)) = 2f (x) -1, x \in \{0,1\}^n\big\}\big) > 0.55\quad ?$$ $g ...
Dattier's user avatar
  • 3,365
1 vote
1 answer
78 views

Understanding statement about bounds of vector in the context of a RSDF ≤ₘ WOPT proof

I'm trying to follow the proof of Lemma 4 of "Strong NP-Hardness of the Quantum Separability Problem", by S. Gharibian, 2010 [1], which, roughly, states that there is a many-one reduction ...
MikeEVMM's user avatar
2 votes
0 answers
98 views

When does Le Cam's method give tight lower bounds for distribution testing?

In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: ...
π314's user avatar
  • 33
2 votes
1 answer
92 views

Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
dohmatob's user avatar
  • 6,338
0 votes
1 answer
263 views

Can finite sets be non-c.e. depending on how they are presented?

I ask the question because of the following statement found in Mark Burgin's paper, "Algorithmic complexity of recursive and inductive algorithms", Theoretical Computer Science 317 (2004) 31-...
Thomas Benjamin's user avatar
-1 votes
1 answer
81 views

Finding a $k$-subset which maximizes a matrix sum

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem: Is there a polynomial-time solution to the following ...
Samrat Mukhopadhyay's user avatar
1 vote
1 answer
135 views

Is Toom's rule robust under local but non-on-site noise?

Toom's rule is a 2-dimensional cellular automaton which is known to have two distinct stationary measures in the thermodynamic limit, even after small perturbations to a probabilistic cellular ...
Andi Bauer's user avatar
  • 2,769
3 votes
0 answers
94 views

Are there (probablistic) uniform 1D cellular automata which can fault-tolerantly store one bit?

In two dimensions, "Toom's rule" is known to be a cellular automaton which can fault-tolerantly store one bit of information. This means that, if we start with the all-0 configuration on an $...
Andi Bauer's user avatar
  • 2,769
3 votes
1 answer
144 views

Is factorial computation known to be in a class smaller than $FEXP$?

Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
Turbo's user avatar
  • 13.4k
0 votes
0 answers
94 views

Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace

Let $q$ be a fixed prime, $P, Q$ be polynomials with $\mathrm{deg}(Q) < \mathrm{deg}(P)$ and $h = O(\log n)$. Let $S$ be a subset of $\mathbb{F}_q^n$ of size $P(n)$ such that there exists a subset ...
cha21's user avatar
  • 328
5 votes
1 answer
284 views

Why is this nonlinear transformation of an RKHS also an RKHS?

I came across this paper (beginning of page 6) where they stated that if $f,h\in \mathcal{H}$, where $\mathcal{H}$ is an RKHS, then $l_{h,f}=\left|f(x)-h(x)\right|^q$ where $q\geq 1$ also belongs to ...
Kashif's user avatar
  • 343
0 votes
1 answer
848 views

How does the greedy algorithm for CSES problem collecting numbers work? [closed]

The collecting numbers problem in the CSES problem set has a greedy solution where we compare the position of a number x with the position of x-1. If pos(x) < pos(x-1) then we increment rounds ...
Ak01's user avatar
  • 101
2 votes
0 answers
175 views

Are there some algorithms which have high consistency strength?

Are there some algorithms, their time complexity is relatively good, for example polynomial time. And the correctness of them has high consistency strength. And these algorithms shouldn't able to ...
Reflecting_Ordinal's user avatar
8 votes
1 answer
410 views

Does the morphism of composition have some universal property?

Let $A$, $B$ and $C$ be three objects in the category Set. For simplicity, assume that their underlying sets contain a finite number of elements, a, b and c respectively. Using the usual Haskell ...
Johan Thiborg-Ericson's user avatar
16 votes
6 answers
5k views

Revisiting the unreasonable effectiveness of mathematics

Question: On balance, with theoretical advances in algorithmic information theory and Quantum Computation it appears that the remarkable effectiveness of mathematics in the natural sciences is quite ...
Aidan Rocke's user avatar
  • 3,639
5 votes
1 answer
183 views

Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$

Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b "=...
Dominic van der Zypen's user avatar
1 vote
1 answer
349 views

Cramer–Castillon problem like

Special case of Golden ratio as a property of conic section (is it known?) as follows: Let $ABC$ be arbitrary triangle and $DEF$ is the its tangential triangle. Let $CF$ meets $AB$ at $G$ and $BE$ ...
Đào Thanh Oai's user avatar

1
2 3 4 5
12