# 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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**4**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**3**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**1**answer

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 ...