All Questions

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.

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

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$?

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

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

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?

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

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

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

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

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

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

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

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

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

Consider the following simple problem (puzzle): given a $N \times N$ $c$-colored grid $G$ a $N \times N$ $c$-colored target grid $G_T$ a number $m$ represented in unary Can we transform $G$ into $...

What is the difference between the following types for the $head$ function on a vector of integers. ($head$ takes a natural number $n$ and a vector $v$ of length $n$ or $(n+1)$ (depending on the ...

I am an engineering student. In our college some subjects chose for elective subjects. That include chooses for Artificial neural network and probability and statistic i'm confused to chose any one ...

For a variant of the TSP problem such that not all vertices have to be visited, is there a way to add a constraint such that the linear program will start at a certain vertex?

In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [...

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

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

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

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

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

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

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

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

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

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

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

Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$? e.g.: $L\notin \...

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...

TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied. Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ...

I already know how to find treewidth with elimination ordering on a tree. But how can I obtain an elimination ordering of width at most k from a tree decomposition of width k?

This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer. I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...

We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program. I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...

I couldn't successfully find relevant work in the time complexity of solving STCONN (in directed graph) in One-Tape Turing Machine. Of course there is a "linear-time" algorithm like DFS/BFS, but is ...

What is the complexity of the following problem? Instance: Simple, undirected graph $G$, and a positive integer $k$. Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...

Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: P1. Find a largest induced subgraph of the ...

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...

Given: $k > 1 $ sales execs, each specializing in one of 4 lines of business (LOBs), where each exec works (sales and travel) at 7.5 hours / day $n > 1$ client sites. Constraints: Each ...

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...

I am trying to linearize a binary quadratic program by a simple linear inequality i.e. for the given objective $\mathbf{\min_{x \in \{0,1\}^n} x^TAx}$, I want to linearize the objective by using ...

Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V_1$ and $V_2$, where for all $v_1\in V_1$, we have $c(v_1)=1$ and for ...

I wonder if there exist topologies for the lambda-calculus where computational divergence (like for $\Omega = (\lambda x. x x) (\lambda x. x x)$) has a topological meaning as the divergence of a ...

Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...

Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...

To prove that two given functions are the same involves proving infinitely many statements. I wonder how to implement so that a computer can check such a statement? An easy example is the following: ...