All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
8 views

Why can methods like ReSuMe, Chronotron and SPAN only train single-layer spiking neural networks?

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 ...
5
votes
0answers
55 views

What are the issues with a set-like interpretation of quantifiers in type theory?

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 ...
-4
votes
0answers
36 views

Reduction from Sudoku to 3SAT [closed]

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 ...
1
vote
0answers
21 views

Can this be formalized as a conversion rule for CoC?

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 ....
-1
votes
0answers
21 views

acquaintanceship graph and six degree of separation relate to each other

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 ...
4
votes
0answers
56 views

What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

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 ...
-2
votes
1answer
107 views

Does such a graph exist?

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 ...
5
votes
3answers
142 views

Type theory and fixed points of datatypes

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 ...
0
votes
0answers
69 views

Practical difference between a $O(n)$ and $O(n^2)$ algorithms [closed]

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)...
0
votes
0answers
43 views

Implementation of vectors as dependent types in CoC

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 ...
-2
votes
0answers
64 views

Does busy beaver function of Riemann hypothesis imply it can be proved in a finite time? [closed]

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, ...
4
votes
1answer
73 views

A counter example for the set mean objective

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) =...
4
votes
0answers
97 views

Complexity of optimal elimination for a planar tensor network

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 ...
2
votes
0answers
39 views

Worst to average case reductions for quantum complexity classes

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 ...
1
vote
0answers
56 views

Properties of the polymorphic type $\Pi t : * . ((t \to t) \to t) \to t$

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 ...
-1
votes
0answers
18 views

In a computer based open system, what theories concern the dealing with system externals? [closed]

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 ...
-1
votes
0answers
33 views

Can computation subsume communication? [closed]

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 ...
3
votes
0answers
60 views

What are some examples of non-algebraic effects?

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 ...
0
votes
1answer
104 views

When should one start looking at existing results in theoretical CS?

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 ...
-2
votes
0answers
24 views

randomized O∗ (3(∆+1)2k )-time algorithm for Special Max Cut [closed]

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)| ...
0
votes
0answers
108 views

What is wrong with the "obvious" approach to function extensionality by providing context-aware rewrites?

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 ...
-1
votes
0answers
30 views

Algorthim for finding traffic equalibrium

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 ...
5
votes
1answer
235 views

Which universities in the U.S. are doing research in type theory?

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 ...
-2
votes
0answers
25 views

How to find the accuracy of LDA model? [closed]

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 ...
8
votes
1answer
112 views

Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

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 ...
-2
votes
0answers
45 views

Polynomial Reduction [closed]

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 ...
3
votes
2answers
105 views

Parameterized complexity of tree/branch decomposition

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 ...
3
votes
0answers
95 views

Detailed proof of Theorem 2.1 in Papadimitrou book (Multitape TM to SingleTape TM)

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 $...
-1
votes
0answers
51 views

Does "clean software architecture" exhibit crystaline structure? [closed]

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 ...
10
votes
0answers
109 views

Fastest Known Algorithm to Count Acyclic Orientations in a Graph

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....
2
votes
1answer
66 views

Why not solve s-sparse recovery on a stream by tracking moments?

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 $...
7
votes
0answers
80 views

Complexity of merging two convex hulls in $\mathbb{R}^d$

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 ...
5
votes
2answers
1k views

Full names of C. K. Chow and C. N. Liu

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
0
votes
0answers
102 views

How to read a COLT or other paper related learning theory?

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 ...
0
votes
1answer
166 views

Is there a precise definition for big O notation with 2 or more variables [closed]

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 ...
0
votes
0answers
24 views

Can we pick a basis for synchronous circuits which coarsens towards the target partition at every layer?

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 ...
3
votes
0answers
92 views

Do random functions have synchronous, alternating circuits with non-injective first layers?

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 ...
-1
votes
0answers
40 views

on kolmogorov complexity technigues

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) ...
5
votes
2answers
96 views

Reference request for linear algebra over GF(2)

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 ...
6
votes
1answer
190 views

Complexity of reachability in directed rooted forests

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 $...
2
votes
0answers
48 views

Complexity of a matrix partition problem in graphs

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 ...
6
votes
1answer
257 views

What is the complexity of HORN-2CNF entailment?

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 ...
3
votes
1answer
129 views

Effect of HoTT/Univalence Axiom on equality between terms of inductive types?

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 ...
0
votes
1answer
107 views

Hardness of computing the dimension of an integral polytope?

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 ...
8
votes
2answers
346 views

Why is the Curry-Howard isomorphism?

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 ...
8
votes
0answers
74 views

Expressiveness of pushdown automata whose stack height sequence is unambiguous

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,...
7
votes
0answers
103 views

Are the non-lazy / non-weak semantics of the $\lambda$-calculus related to weak evaluation?

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{...
2
votes
0answers
32 views

Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?

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 ...
-2
votes
0answers
51 views

Vertex pairs connected by path of weight zero

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 ...
6
votes
0answers
150 views

"Looking for help understanding a proof by Gossner (1998)."

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

15 30 50 per page
1
2 3 4 5
232