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.
548
questions
1
vote
1answer
247 views
Cramer–Castillon problem like
Cramer–Castillon problem being very difficult problem. Related to the Cramer–Castillon problem configuration, I posed a problem as follows:
Let $ABC$ be arbitrary triangle and let three collinear ...
1
vote
1answer
568 views
Turing's fixed-point theorem
Motivation:
It recently occurred to me that Turing's analysis of the halting problem may be formulated as a fixed-point theorem. Might this intuition from theoretical computer science have informed ...
1
vote
0answers
74 views
constructive type theory references books
What is the best book you recommend for a beginner in constructive type theory applied to computer science?
2
votes
1answer
83 views
Busy beaver sequence for a simple tag-like system
This question arose in the context of tag-like systems, specifically Bitwise Cyclic Tag (BCT). Consider the following discrete dynamical system:
Let $\mathbb{B} = \{\mathtt{0}, \mathtt{1}\}$. Let our ...
1
vote
0answers
40 views
Encryption based on boolean satisfiability?
We got sketch of algorithm for public key encryption based on satisfiability
of hidden boolean formula. It is easy to break
in its current form, but we are interested if it can be improved.
Alice ...
4
votes
1answer
86 views
String compression algorithms for simplifying an expression by introducing variables
I have a very long algebraic expression computed with Maple, and when I inspect it visually, it is clear that it consists of a set of terms that appear over and over again. For purposes of human ...
1
vote
1answer
65 views
Algorithms for Polynomials Over a Real Algebraic Number Field, a reference
I need to find "Algorithms for Polynomials Over a Real Algebraic Number Field
Ph.D. thesis, University of Wisconsin, Madison (1974) by Rubald". However I cannot find it online nor in my ...
2
votes
0answers
70 views
Is this variant of bitwise cyclic tag Turing-complete? [closed]
Cross-posted from Theoretical Computer Science.
CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply ...
1
vote
1answer
54 views
Proving that a preorder traversal of a rooted tree $T(V, E)$ is $O(\lvert V \rvert)$ [closed]
Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \...
3
votes
0answers
56 views
CCCs, computational calculi and point-surjectivity
The models of some computational calculi are in a correspondence with Cartesian Closed Categories with an object $U$ that has some relationship to its exponential object $U^U$ e.g. a retraction ...
2
votes
1answer
128 views
Largest number N for which injective mapping $f: 2^N \to 2^8 \times 2^8 \times 2^8$ which is Lipschitz-1 CT with $K\leq 3$ exists
I have a function on $h: [0,1] \to [0,1]$ whose output is smooth (polynomial of low degree), and I need to discretize it but I need to save it with three 8 bit numbers. These three 8 bit numbers need ...
2
votes
1answer
117 views
Monotonicity of Dirichlet form of Markov chain
Consider a continuous-time, irreducible Markov chain $X_t$ on a finite state space $E$. Assume the jump rates are $R(x,y)$ for $x,y\in E$, the generator is $L$, i.e for any function $f$ on E,
$$Lf(x)=\...
0
votes
1answer
153 views
Algorithmically decide if an algorithm has optimal time complexity [closed]
Is there an algorithm with the following input and output?
INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs.
OUTPUT: "YES"...
0
votes
1answer
168 views
Maximize sum of edge weights on spanning tree
Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$.
Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
2
votes
1answer
251 views
Is there a term for a subgraph which includes all the edges of a graph?
A subgraph is called spanning when it includes all of the vertices of the given graph.
Is there a term for a subgraph which includes all the edges of a graph?
Thanks.
3
votes
0answers
149 views
Games and the right mathematical framework for GANs
Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations.
It is an important topic within deep learning.
Are ...
1
vote
0answers
46 views
Polynomial sized arithmetic map from circle to ellipse preserving integral points
Let $n$ be a square free integer and a product of $O(m/\log m)$ number of primes $1\bmod 4$ where $m$ is $\log_2n$.
Take the circle around origin of radius $n^2$. It has ${\exp}(m/\log m)$ number of ...
7
votes
2answers
466 views
Does there exist a process to build a list of numbers whose standard deviation is an integer?
Or rephrased, is there a way to make a list of numbers whose sample variance is a square number? I'm interested in sequences of arbitrary length with integer elements.
(I come from a computer science ...
2
votes
0answers
72 views
Finding k elements with count queries
Given a 'count in range' query access to an array of $N$ elements, our goal is to find $K$ missing elements with as few queries as possible (worst case, deterministic).
To clarify, we can query
how ...
1
vote
0answers
28 views
Restriction of Rademacher Complexity
Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...
3
votes
1answer
112 views
What is the name for Boolean algebra's version of $\models$ between sets of identities and identities?
On p62 in Schaum's Outline of Theory and Problems of Boolean Algebra and Switching Circuits by Elliott Mendelson (1970),
Part (b) of the corollary says that if an identity is satisfied by some ...
-2
votes
1answer
197 views
Is equational logic in universal algebra a proof system not a logic system?
As far as I know a logic system defines its own semantics (e.g. $\models$), but not a proof calculus/system on its language. See p261 in Ebbinghaus et al's Mathematical Logic:
In universal algebra, ...
7
votes
4answers
229 views
Discretizing a line segment with pixels which satisfies the Pythagorean theorem
There are plenty of line drawing algorithms to discretize line segments using pixels.
The Bresenham's algorithm gives a line where the number of pixels in the segment is the same as its width (in x-...
2
votes
1answer
273 views
Can primitive recursive functions be simulated in the smallest reasonable primitive recursive group?
Second Edition, completely rewritten with unchanged questions.
The said questions are motivated by the bizarre wording of the concluding § in A Class of
Reversible Primitive Recursive Functions by L. ...
7
votes
1answer
239 views
Search algorithms with mappings/functions/sets as variables
I apologize in advance if this sounds vague but I am trying to find directions as to what to look for.
All the sets in this problem are finite.
Suppose we have two functions $f_1\colon X_1\times Y_1\...
2
votes
0answers
45 views
Deduction theorem for the modal mu-calculus
Does the modal mu-calculus have a deduction theorem?
If yes, how is it stated? Does it have the 'classical' form (i.e. as in classical propositional logic) or is it more involved?
1
vote
1answer
63 views
How do I fit flow values to connections in a known network?
This is not my area and I'm new to its terminology, and am posting my problem in the hope that someone will be able to direct me to where it has been solved, or who has written about it.
I have a flow ...
6
votes
1answer
287 views
Probability of complex eigenvalues
I find this is the best site to post this question, even though I considered cs.
It is a Monte Carlo experiment over the set of 10.000 n×n matrices.
If a single matrix eigenvalue is complex then ...
2
votes
1answer
260 views
Is good reduction decidable?
Let $X$ be a smooth projective geometrically connected variety over $\mathbb{Q}$. It is said to have good reduction at a prime $p$ is there is a smooth projective $\mathcal{X}\to \mathrm{Spec}\:\...
6
votes
0answers
123 views
On thinking of spacetime as a local Scott domain
An observation of Martin and Panangaden links the study of Lorentzian manifolds and the semantics of programming languages via the theory of Scott domains.
Background:
Recall that if $M$ is a time-...
179
votes
3answers
91k views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
5
votes
1answer
180 views
NP-hardness of a sequence problem
Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
8
votes
0answers
152 views
Does the “coproduct-elimination transform” have an accepted name, and where can I learn more about it?
Suppose we're in a bicartesian closed category. Then given a morphism $$f : X \rightarrow Y_1 + \ldots + Y_n$$ and a test object $T$, we get a corresponding morphism
$$T^f : X \times [Y_1,T] \times \...
0
votes
0answers
11 views
Is there a way to solve the optimal branching / arborescence problem with path-dependent weights?
The optimal branching problem (solved by Edmond's algo or Tarjan's algo) finds the spanning arborescence for a particular graph. [0]
I'm looking for a formulation of the problem that allows for path-...
0
votes
0answers
78 views
Vertex cover algorithm
Given a graph $G(V, E)$, remove the vertex (or one of the vertices) with the highest cardinality from $G$ and put it in a list $L$. Repeat until in $G$ there are only vertices with cardinality $0$ (no ...
1
vote
0answers
121 views
Checking existence of proofs of fixed length
This question is a continuation of a related previous question (check here).
Let $\mathcal{L}$ be a recursive first-order theory with the Hilbert-Ackerman's proof calculus, and such that the ...
0
votes
0answers
72 views
Fast double exponentiation in finite fields
Let $p$ be a prime, and let $\mathbb{F}_p$ be the finite field with $p$ elements. Let $a$ be a non-zero element of $\mathbb{F}_p$. Can we quickly evaluate $a^{2^r} \mod{p}$? Using repeated squaring, ...
43
votes
4answers
897 views
How to write computer-assisted mathematics well?
Much has been said about writting good papers in mathematics. A short google query yields countless sources of advice. This skill also appears to be quite transferrable between basic branches of ...
0
votes
1answer
103 views
Unknown notation in “Boolean function complexity” by Stasys Jukna [closed]
I am currently reading Boolean Function Complexity - Advances and Frontiers by Stasys Jukna and on page 7 of the latest edition there is a paragraph titled Boolean functions as set systems with the ...
0
votes
1answer
77 views
Maximum-weight perfect matching in a 3-regular, complete, 3-partite hypergraph
Let $H=(V, E)$ be a weighted hypergraph such that $V=A\cup B \cup C$, where $A,B,C$ are disjoint sets of size $n$, and $E=A\times B\times C$. In my particular case, $\forall e\in E$, $ wt(e)\in\{0,\pm ...
1
vote
1answer
153 views
Upper bounding VC dimension of an indicator function class
I would like to upper bound the VC dimension of the function class $ F$ defined as follows:
$$ F := \left\{ (x,t) \mapsto \mathbb{1} \left( c_Q\min_{q \in Q} {\|x-q \|}_1 - t > 0 \right) \; | \; Q ...
0
votes
0answers
19 views
Finding resulting lobe of product of anisotropic Spherical Gaussians
Fisher Bingham (Isotropic) case
For my current research I am trying to find the parameters of the product of 2 ASG (anisotropic spherical Gaussians).
A common spherical Gaussian formula (SG) is:
$...
1
vote
0answers
27 views
Modified straightline complexity of almost square of sums
Assume every linear operation (such as inner product with constant vector) can be performed in one step and multiplication by variables (quadratic operation) can be performed in one step.
We know the ...
0
votes
0answers
114 views
Lower bounds on the length of circuits, depending on the number of times it crosses itself
I have this problem that I have been stuck on for months, and would like to know if somebody can tell me a way to attack the problem. Let me ask the problem in a simple example below.
Let $G(V,E)$ be ...
0
votes
1answer
78 views
Value (not position)- based sorting; reference request
A recent answer of Ville Salo on the diameter of a Cayley graph induced by bubble sort generators (adjacent transpositions) has inspired this variation.
Many sort algorithms are position based: you ...
5
votes
0answers
318 views
Can information be extracted more precisely using more random trials?
Write $n$ iid draws of $(x,y)$ as $(x^n, y^n)$. Fix $R\in (0,H(x))$. What is the min of $n^{-1}H(y^n|f(x^n))$ over $f$ with $H(f(x^n))\leq nR$, taking $n\to \infty$?
3
votes
1answer
75 views
What is known about computing all binary error correcting codes of given parameters?
Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$.
Are there any sources about using algorithms to find all given ...
5
votes
3answers
183 views
Minimum number of swaps needed to 'group' a sequence?
Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
4
votes
0answers
66 views
Amortized complexity of P
Let $P$ be the class of all polynomial time computable functions from $\{0,1\}^*\rightarrow \{0,1\}$. For any $f\in P$, define function $f^A:\mathbb{N}\rightarrow \{0,1\}^*$ by
$$f^A(n)=(f(x_1),\cdots,...
-4
votes
1answer
291 views
PCP theorem to check hard proofs [closed]
Is it technically possible to check formidable proofs like Mochizuki's using PCP theorem before mathematicians spend time in understanding the mechanics of the proof? If so why have mathematicians not ...
