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

573
questions

4
votes

0
answers

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

0
votes

1
answer

60
views

### Recursive function - proof by induction

Let $\Sigma$ denote an alphabet and $[ \Sigma ]$ set of lists.
I've encountered the following function:
$f([])=[]$
$f([x])=[x]$, for $x \in \Sigma$
$f(x:L)=f(L)$, for $x \in \Sigma$ and $L \in [ \...

2
votes

0
answers

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

0
votes

0
answers

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

7
votes

1
answer

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

2
votes

1
answer

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

9
votes

1
answer

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

5
votes

2
answers

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

1
vote

1
answer

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

5
votes

1
answer

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

3
votes

1
answer

195
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 $\...

2
votes

0
answers

133
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, $\...

1
vote

1
answer

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

1
vote

1
answer

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

2
votes

0
answers

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

1
vote

1
answer

50
views

### Optimal number of half-spaces in H-representation of convex-hall 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-...

0
votes

0
answers

21
views

### Optimal distribution on $k$-dimensional subspaces of $R^n$ which maximizes $\mathbb E_{V \sim D}\|Proj_V(x)\|^2$, given side informaiton on fixed $x$

Let $d$ be a large integer and let $ k \in [1,d]$ be another integer. Let $V$ be uniform over the grassmannian $G_{k,d}$ of $k$-dimensional subspaces of $\mathbb R^n$, and let $P_V:\mathbb R^n \to \...

0
votes

1
answer

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

-1
votes

1
answer

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

1
vote

1
answer

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

3
votes

0
answers

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

3
votes

1
answer

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

0
votes

0
answers

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

4
votes

1
answer

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

0
votes

1
answer

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

2
votes

0
answers

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

0
votes

0
answers

49
views

### Logical operations expressed as polynomials

Suppose that $x,y\in\{0,1\}\subset \mathbb{F}$, where $\mathbb{F}$ is a field, which can be assumed of characteristic 0 or arbitrarily large. It is plain that the standard logical operations can be ...

8
votes

1
answer

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

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

5
votes

1
answer

172
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 "=...

1
vote

1
answer

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

1
vote

1
answer

686
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

120
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

106
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

47
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

105
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

77
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

94
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

67
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, \...

7
votes

0
answers

89
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

147
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

141
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

187
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

292
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

580
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

1
answer

219
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

50
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

530
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

74
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

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