# All Questions

10,396 questions
Filter by
Sorted by
Tagged with
25 views

### 2 Approximation for Steiner tree

Considering the Steiner tree Problem on a complete Graph with metric distances, I am searching for a 2 approximation algorithm. Preferable with a factor better than 2.
23 views

### Is the transducer version of BPP closed under complement?

Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this ...
27 views

### On classes $UP$ and $US$?

Is there any consequence if the classes $UP$ and $US$ have complete problems? $coNP$ is in $US$ according to https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us and does $NP$ also belong to $US$?
23 views

### What is the state of the art in first order stochastic convex optimization?

What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD? What is the optimally fastest convex function minimizing algorithm which ...
29 views

### Implementations of Dependent Type Theory

I am trying to find a minimal implementation of dependent type theory that supports Pi Types (obviously) Modules containing records Inductive data types Universe Hierarchy A notion of equality ...
21 views

### Conjuagate operation solution

Let A,B two matrices over binary field that are similar. So there exists a solution to equation of type $$B=gAg^{-1}$$ Is there an algorithm to find all g's? May be a quantum algorithm?
65 views

### Complexity of unbalanced bipartite isomorphism

For $i=1,2$, let $G_i=(A_i\cup B_i,E_i)$ be an undirected bipartite graph with bipartition $A_i$ and $B_i$, where $|A_1|=|A_2|=a$ and $|B_1|=|B_2|=b$ with $a\le b$. Question. Is the problem of ...
68 views

### Extended Church's thesis and internal parametricity

I am wondering if there is any known relationship between these 2 concepts in intensional MLTT as formulated here. Does $Internal\ parametricity \implies ECT$ hold? For forumlation of ECT see https://...
108 views

### Assuming P != NP, what is the cardinality of the set of NP-Hard languages? [on hold]

Clearly if P = NP, then every non-trivial language is NP-Hard, so there are uncountably many NP-Hard languages. However, assuming P != NP is NP-Hard known to be uncountable? My guess would be yes, but ...
38 views

### Lack of atomic propositions in the Calculus of Constructions from ATTAPL textbook

I am working through the Dependent Types chapter from Advanced Topics in Types and Programming Languages (ATTAPL) by Benjamin Pierce et al. I am confused with the calculus presented Fig 2-7 (Calculus ...
14 views

### Efficient Graph Affinity Matrix Computation

I need to compute an affinity matrix for an unweighted undirected graph of related musical artists for the purposes of spectral clustering. Now, the most obvious affinity measure to use is shortest ...
40 views

### Proposition terms vs types in Coq

Consider the following div function written in Coq. It takes in a proof that the divider is non-zero. Definition div (n d:nat) (pf: ~(d = 0)) := n/d. Focus on <...
38 views

### What's the point of Tour Creation Algorithms for TSP if Tour Improvement ones exist? [on hold]

I'm pretty new to the whole Theoretical CS stuff so forgive me if this is a stupid question. I've been researching the different basic heuristics for solving TSP, and have found that there are two ...
107 views

### How to define list zipping categorically/inductively?

Lists and fixpoints The type of $A$-lists is defined as $\mu F_A$, where $F_A(X) = 1 + A \times X$ is the "cons-or-nil"-functor and $\mu$ is the least fixpoint operator. In Haskell syntax, this would ...
88 views

### A Simple Auction Game

You are playing the following game. You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a ...
69 views

73 views

### Is ASM a regular language? [migrated]

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
33 views

### Deterministic One-tape Turing Machine [closed]

What's the procedure to find the middle letter of a word input using a turing-machine?
39 views

### Complexity of recognizing unit distance graphs

A Graph is Unit Distance Embeddable (UDE) if it can be embedded in the plane such that every edge has a length of 1. A minor of a UDE graph is also UDE so by the Graph Minor theorem, there must be a ...
64 views

### Does Descriptive Complexity techniques have the naturalisation barrier?

I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise? By naturalise I'm talking about the Idea of Natural ...
292 views

### PHOAS with extrinsic typing?

Parameterized Higher Order Abstract Syntax (PHOAS) is a representation of syntax trees that allows the host language's binding to be used to represent binding in the language being modelled, while ...
229 views

### Consequences of BPP=BQP

If BPP=BQP then there is a polynomial time randomized factoring algorithm. A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, ...
93 views

### Can the aliens hustle us with Chaitin's constant?

Premise Suppose you are an alien and want to fool Earthlings you have extracted the value of Chaitin's Constant. Does the strategy below work? If so, any explicit(/basic ideas for) algorithm? If not, ...
46 views

I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly ...
139 views

### Maximum shortest word accepted by pushdown automata

Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic ...
23 views

### Relation between bi partite graphs and neural network diagram? [on hold]

I came across a bi partite graph from network flow problems in my algorithms class, the graph has a resemblance to artificial neural network diagram. Is there any relation between the two ? can ...
72 views

### The number of words of length $n$ in a context-sensitive language

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$. What is known about $s_{L}(n)$? Note that it is known that $s_{L}(n)$ is either polynomial,...