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.
641 questions
1
vote
1
answer
43
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 ...
- 111
1
vote
0
answers
30
views
M-char reduction inverse Theorem [closed]
I need a bit of help finishing this theorem I believe it to be true. First, set $\mathcal{B} = \{A, B, \dots, Z\}$ to be the set of capital letters in base 64, and define $\mathcal{A}_m$ as the set of ...
- 317
6
votes
2
answers
735
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 ...
- 6,652
71
votes
10
answers
20k
views
Relating category theory to programming language theory
I'm wondering what the relation of category theory to programming language theory is.
I've been reading some books on category theory and topos theory, but if someone happens to know what the ...
- 21.3k
5
votes
1
answer
469
views
Is the set of generalized Fermat triples computable?
Is $\;\big\{(a,b,c)\in\mathbb{N}^3: \big(\exists m,n,\ell \in (\mathbb{N}\setminus\{0,1,2\})\big): a^m + b^n= c^\ell\big\}\;$ computable?
- 651
59
votes
10
answers
26k
views
Problems known to be in both NP and coNP, but not known to be in P
One such problem I know is integer factorization.
What are other interesting cases?
- 28.2k
6
votes
0
answers
102
views
Computer program for free restricted Lie polynomial
I am conducting numerical experiments involving the Gröbner–Shirshov Basis for restricted Lie algebras. At each step of the computation, I need to work with restricted Lie polynomials. Specifically, I ...
- 63.9k
3
votes
1
answer
103
views
References: rigorous algorithms for elementary computations in base-b with complexity estimates
Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by
$$\mathcal{X}(b,M):=\{x\in \...
- 63.9k
1
vote
1
answer
197
views
Probability distribution on Python-dictionary-like objects?
I would like to examine information-theoretical properties of random variables that take as values objects which are akin to dictionaries in the Python programing language.
That is, each sample of the ...
CommunityBot
- 1
3
votes
0
answers
120
views
References on P vs NP under various axiomatic systems
I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem.
This problem has resisted attacks ...
- 31
17
votes
2
answers
2k
views
Efficiently determine if convex hull contains the unit ball
Given a set of $n$ points in $\mathbb{R}^d$, is there an algorithm to determine if the convex hull contains the unit ball centered at the origin in polynomial time (in both $n$ and $d$)? The convex ...
- 221
1
vote
0
answers
37
views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function
$$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$
Can we find all the ...
- 11
8
votes
1
answer
719
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 ...
- 48.9k
9
votes
1
answer
1k
views
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
1
vote
1
answer
284
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 ...
CommunityBot
- 1
6
votes
1
answer
501
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 ...
CommunityBot
- 1
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
3
votes
1
answer
315
views
About Shor's quantum algorithm
I know very little about quantum computing, and I've been trying to understand Shor's algorithm for the factorization of an integer $N$. I'm following Computational Complexity — a modern approach by ...
- 731
7
votes
1
answer
757
views
compression of a Turing machine run sequence
consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...
CommunityBot
- 1
1
vote
0
answers
78
views
On binary constraints defined by vanishing of bivariate polynomials modulo $n$ [duplicate]
In an answer here
Dima Pasechnik showed that constraints of the form $x_i x_j + a_{ij}x_i + b_{ij}x_j + c_{ij}$ are efficiently solvable modulo $2$ using Groebner basis.
In comments he suggested that ...
- 25.4k
1
vote
0
answers
31
views
Multipoint evaluation in Lagrange basis on subset smaller than degree
Setup. Let $\mathbb{F}$ be a finite field with a multiplicative subgroup $E = \{e_1, \dots, e_k\}$ of order $k$. Given a list $y = y_1, \dots, y_k\in \mathbb{F}$ let $p$ be the unique polynomial of ...
2
votes
0
answers
122
views
What do we know about efficiently finding a solution to a system of multivariate polynomials over finite fields?
Consider the following (NP-complete) problem:
Given a system of polynomials $f_1, f_2, \ldots, f_m \in \mathbb{F}_q[x_1, x_2, \ldots, x_n]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational ...
- 121
35
votes
12
answers
4k
views
Open questions about posets
Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...
- 1,644
0
votes
0
answers
106
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), ...
- 34.3k
2
votes
0
answers
173
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 ...
- 5,407
1
vote
1
answer
91
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 ...
- 1,299
4
votes
1
answer
342
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 ...
- 3,319
2
votes
0
answers
41
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 ...
- 129
8
votes
1
answer
3k
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 ...
- 188k
0
votes
3
answers
402
views
boolean functions and averaging / counting
Hey guys,
I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...
- 18.4k
1
vote
2
answers
198
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 $...
- 109k
3
votes
1
answer
386
views
Hermit H-machines
I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...
- 236k
1
vote
1
answer
168
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 ...
- 48.9k
0
votes
2
answers
96
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 ...
- 23.7k
5
votes
1
answer
2k
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 ...
- 30.3k
12
votes
2
answers
2k
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 ...
- 30.3k
4
votes
1
answer
463
views
Turing Machine which generates order on the set of its states
This question is related to this one Do Turing Machines generates any nontrivial lattice on the set o symbols or states?
The Turing machine (TM) is an abstract model for effective implementation of (...
- 4,219
1
vote
0
answers
62
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
83
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
95
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 ...
- 6,353
9
votes
3
answers
602
views
Admissibility of Harrop's rule, computationally
It is obvious that the following formula is not a theorem of
intuitionistic propositional calculus (IPC).
$$
(\neg A \; \to \; B \vee C) \;\; \to \;\;
((\neg A \; \to \; B) \vee (\neg A \; \to \; ...
- 6,353
1
vote
0
answers
66
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 ...
- 151
35
votes
3
answers
5k
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....
- 245
1
vote
0
answers
119
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. ...
- 1,313
-5
votes
1
answer
79
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
- 2,992
0
votes
1
answer
75
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 ...
3
votes
0
answers
85
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 ...
4
votes
0
answers
214
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 ...
- 24.2k
3
votes
1
answer
308
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 ...
- 81