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
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$ ...
user avatar
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 [ \...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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{...
user avatar
  • 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(...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$....
user avatar
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 $\...
user avatar
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, $\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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-...
user avatar
  • 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 \...
user avatar
  • 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-...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 "=...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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, \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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)=\...
user avatar
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"...
user avatar
  • 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]$, ...
user avatar
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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
12