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$ ...
- 309
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 [ \...
- 31
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 ...
- 1,039
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 ...
- 716
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{...
- 6,286
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(...
- 6,286
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 ...
- 39.4k
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 ...
- 39.4k
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$....
- 39.4k
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 $\...
- 39.4k
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, $\...
- 39.4k
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 ...
- 3,019
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 ...
- 11
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: ...
- 33
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-...
- 5,580
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 \...
- 5,580
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-...
- 5,744
-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 ...
- 2,525
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 $...
- 2,525
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 ...
- 12.8k
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 ...
- 328
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 ...
- 323
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 ...
- 1
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 ...
- 287
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 ...
- 3,203
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 "=...
- 39.4k
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,390
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 ...
- 3,203
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?
- 21
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,577
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 ...
- 23.3k
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 ...
- 3,668
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 ...
- 377
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,577
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, \...
- 19
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 ...
- 121
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)=\...
- 21
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"...
- 1
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]$, ...
- 11
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.
- 337
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 ...
- 12.8k
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 ...
- 12.8k
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 ...
- 79
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 ...
- 21
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 ...
- 1