Problem Detail: Natural numbers are defined inductively as (using Coq syntax as an example) Inductive nat: Set := | O: nat | S: nat -> nat. Is there a standard way to define integers (and maybe other sets like rationals and Read More …
Blog
[Solved]: Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space
Problem Detail: We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): Leftrightarrow i geq 0$. We don’t know in advance how many elements of $S$ satisfy the predicate $P$, Read More …
[Solved]: Tool/app for learning category theory?
Problem Detail: Being a programmer I appreciate the errors given by a compiler for a programming language and come to rely on the compiler’s error as a safety net. In learning category theory I would like to have some tool that Read More …
[Solved]: A lambda calculus evaluation involving Church numerals
Problem Detail: I understand that a Church numeral $c_n$ looks like $lambda s. lambda z. s$ (… n times …) $s;z$. This means nothing more than “the function $s$ applied $n$ times to the function $z$”. A possible definition of the Read More …
[Solved]: Showing that Independent set of size $k$ can be decided using logarithmic space
Problem Detail: An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-text{IND}$ asks if there is an independent set of Read More …
[Solved]: Complexity of a subset sum variant
Problem Detail: Is this variant of the subset sum problem easy/known? Given an integer $m$, and a set of positive integers $A = {x_1, x_2, …, x_n}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = Read More …
[Solved]: Are probabilistic search data structures useful?
Problem Detail: A SkipList provides the same $O(log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn’t necessary. Since the SkipList is constructed using random coin flips, these bounds only hold as long as the structure Read More …
[Solved]: Can be non-deterministic Turing machine simulated by $k$-tape deterministic TM where $k=infty$ with preserving polynomially-same accepting times?
Problem Detail: I know that for every $k$-tape DTM that runs in time $O(t(n))$, there exists a 1-tape DTM that runs in $O(t^2(n))$, no matter how large the $k$ (the $k$-part is a formulation from Wikipedia). But what if $k=infty$? If Read More …
[Solved]: What does it mean for a random number generator’s sequence to be only 1-dimensionally equidistributed?
Problem Detail: Whilst reading up on Xorshift I came across the following (emphases added): The following xorshift+ generator, instead, has 128 bits of state, a maximal period of 2^128 − 1 and passes BigCrush: [snip code] This generator is one of Read More …
[Solved]: User level threads are transparent to the kernel?
Problem Detail: Find whether given statement True or False? Explain. User level threads are transparent to the kernel? My attempt : False. Since, user level threads are managed by a user level library however, they still require a kernel system call Read More …
