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

1
2 3 4 5
11