All Questions

ReSuMe, Chronotron and SPAN all use STDP-like local learning rules to implement their training algorithm (though they approach the training differently, e.g. SPAN uses gradient descent via spikes ...

In his answer to a question that tries to treat universal and existential quantifiers as intersections and unions of sets, Andrej Bauer says: Forget the intersections and unions. People get this idea ...

Consider following problem from this file You are given a $n^2 × n^2$ grid where every entry is either blank or contains a numbers from $\{1, 2,..., n^2\}$. The goal is to decided whether the ...

Consider the Church encoding of booleans in CoC $$ Bool := \forall t : * . t \to t \to t \\ T := \lambda t : * . \lambda x : t . \lambda y : t . x \\ F := \lambda t : * . \lambda x: t . \lambda y : t ....

The picture which will be used to draw an acquaintanceship graph. Draw the acquaintanceship graph that represents that Tom and Patricia. Tom and Hope, Tom and Sandy, Tom and Amy, Tom and Marika, Jeff ...

Consider a distribution $\mathcal D$ over the reals, a real parameter $H\in\mathbb R^+$, and an integer parameter $k\in\mathbb N$. The Entropy-Constrained Quantization problem asks what is the best ...

In the course of my studies on graphs I sometimes use gadgets. I am trying to construct such a gadget: an edge-colored graph $G$ that has at least one properly colored spanning tree (that is, no two ...

For the purposes of this question, say that a datatype is a type constructor with one type parameter (this is sometimes called a type operator). In Haskell, we can define a fixed point ...

I have been watching this interesting introduction on Quantum Computational Complexity by R. Laumann. At time 1:11:00 (approximately) he gives a qualitative example on the practical difference of $O(n)...

I'm trying to understand dependent types in CoC and I am having trouble finding examples that are actually carried out in CoC, specifically without inductive types or pattern matching. The most ...

I am not computer science background, just came across a paper https://www.scottaaronson.com/busybeaver.pdf We present a 5,372-state Turing machine that encodes Riemann’s hypothesis; in other words, ...

Let $\mathcal{P} = \{P_1, \cdots,P_n\}$ be a family of finite point sets in $\mathbb{R}^d$, each having at most $m$ points. Consider the following objective function \begin{align} cost(\mathcal{P},c) =...

Suppose we need to sum out variables in a tensor network (a factor graph where each variable appears in 2 factors). What is the cost of finding an optimal summation strategy? For instance, compute the ...

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...

In the context of pure type systems (say Calculus of Constructions) I am looking for references discussing the properties of the following polymorphic type: $\Pi t : * . ((t \to t) \to t) \to t$. What ...

I regard computation theories (with lambda calculus for the most typical example, and Turing machine etc.) concerning the dealing with system internals very well studied, but find too little ...

Pondering with ideas around the Actor model vs Turing model besides other related formalizations, I can't help but come to this question: Can computation subsume communication? I believe that within a ...

In this (the only at time of writing) answer to How to tell if an effect is algebraic? informative positive examples are given. But I suppose that's less complete without negative examples, to ...

I'm currently a PhD student in theoretical computer science. I've been working on this problem daily for almost a month that has been well studied and was assigned to me by my advisor. The problem is ...

we are given an undirected graph G of maximum degree ∆, and two integers k, t ∈ N0. The objective is to decide whether there exists a partition (A, B, C) of V (G) such that |A| = |B| = k and |E(A, B)| ...

There is an obvious, dirty and probably wrong approach that allows one to prove function extensionality in a straight-forward manner: provide an equality primitive with a context-aware rewrite. For ...

I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...

The question is meant to be broad in that recommendations with mentions of the particular areas within type theory research are greatly appreciated. Also, the research need not be conducted in ...

I am working on topic modeling using the latent Dirichlet allocation model. I have a dataset that contains tweets and topics corresponding to these tweets. In total, there are 65 different topics. I ...

It is mentioned in multiple papers [1], [2] that $MODp \circ MODq$ circuits for two distinct primes $p, q$ can compute arbitrary functions in exponential size. However, [1] provides no citation for ...

When we have two theories in the same complexity class. Can they always be reduced to each other in polynomial time and space? I know this is true for problems in NP but what's about problems in ...

I'm looking for an up to date reference for parameterized complexity of tree and branch decompositions. IE, complexity of finding tree/branch decomposition of optimal width in terms of relevant graph ...

I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $...

I was thinking today about an analogy between entropy/crystal structure (in the domain of physics) and object-oriented polymorphism. Uncle Bob Martin always talks about how high-level components must ...

Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....

A slightly simplified version of $s$-sparse recovery streaming problem is the following. We get a stream of $n$ elements of the form $(x, \Delta)$, where $x \in [u]$ is a member of the universe, and $...

Given two convex hulls $C_1, C_2$ in $\mathbb{R}^2$ or $\mathbb{R}^3$, it is known how to merge the two convex hulls into a a third convex hull $C$ (the convex hull of the points in $C_1, C_2$) in ...

Where can I find the full names of C. K. Chow and C. N. Liu, of the Chow-Liu tree fame? https://en.wikipedia.org/wiki/Chow%E2%80%93Liu_tree https://ieeexplore.ieee.org/document/1054142

I am a master student right now. And first time met the theoretical computer science, I am really interested in it, and especially the learning theory part. Wish to do research about this part in the ...

Big O notation has a very precise definition for 1 variable. You can prove O(2x^2) = O(x^2) for example. There is never ambiguity. However, for 2 or more variables ...

Given a Boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ and a Boolean basis for circuit gates $B$ (for instance $B = \{AND, OR\}$), we can construct the set of size optimal synchronous (Harper ...

After discussing in the comments, I think a clearer definition of the question is as follows: for a random function $f : \{0, 1\}^n \rightarrow \{0, 1\}$, what is the probability that there exists a ...

A lossless data compression scheme is a pair (f, g) of computable functions f, g : {0, 1} ∗ −→ {0, 1} such that, for all x ∈ {0, 1} g(f(x)) = x Prove: For every lossless data compression scheme (f, g) ...

I have been looking for materials on the linear algebra over $GF(2)$ but so far I haven't found any substantial textbooks or notes on this subject. In fact in one of the notes I found the introduction ...

I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $...

All graphs in this question are finite, simple, and undirected. Let $H$ be a regular graph on at least five vertices, let $v_1,v_2,\dots,v_n$ be the vertices in $H$, and let $M$ be the adjacency ...

I know the entailment of a propositional variable in a HORN-3CNF formula is $P$-complete. I can't find any publication in which it has been shown the complexity of the same problem for HORN-2CNF ...

It is well known that Univalence contradicts Axiom K, for example there are two ways $\mathbf{2} = \mathbf{2}$ may be proved using Univalence, via $\mathtt{id}_{\mathbf{2}}$ or $\mathtt{not}$. But ...

Given a set of linear inequalities $Ax \leq b$ let $P = \text{conv}\{x \in \{0,1\}^n \mid A x \leq b \}$ be the convex hull of all binary vectors that satisfy the given inequalities. I am interested ...

The Curry-Howard isomorphism is the correspondence between type systems (like for the simply typed lambda calculus) and proof systems (like natural deduction). More precisely, types resemble ...

I consider pushdown automata on an alphabet $\Sigma$, which are intuitively finite automata with a stack. Formally, a pushdown automaton $A = (Q, q_0, F, \Gamma, \Delta)$ is a finite set $Q$ of states,...

Vague question The most common semantics of the call-by-name $\lambda$-calculus (Hyland/Wadsworth’s observational equivalence $\approx_\text{HNF}$ and Morris’s observational equivalence $\approx_\text{...

Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question. An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around ...

Consider a graph $G = (V, E)$ where edge $e \in E$ has a weight $w_e \in \{+1, -1\}$. The goal is to enumerate all vertex pairs $(s,t)$ such that $s$ and $t$ are connected by a path (repetition of ...

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...