All Questions

Filter by
Sorted by
Tagged with
-4
votes
0answers
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.
1
vote
0answers
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 ...
-3
votes
0answers
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$?
1
vote
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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?
2
votes
1answer
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 ...
1
vote
1answer
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://...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 <...
-2
votes
0answers
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 ...
5
votes
2answers
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 ...
0
votes
1answer
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 ...
3
votes
0answers
69 views

Reconstructing a colored grid with vertical and horizontal shifts

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

Differences in the type signatures using dependent types

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

What is better to chose as field probability and statistic or ANN? [closed]

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

Linear programming TSP variant constraint formulation [on hold]

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?
1
vote
0answers
52 views

communication complexity lower bound for computing median

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 [...
0
votes
0answers
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 ...
-3
votes
0answers
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?
-2
votes
0answers
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 ...
0
votes
0answers
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 ...
8
votes
1answer
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 ...
5
votes
1answer
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, ...
-2
votes
0answers
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, ...
1
vote
1answer
46 views

About estimating escape time of gradient Langevin dynamics

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 ...
5
votes
2answers
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 ...
-1
votes
0answers
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 ...
2
votes
0answers
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,...
1
vote
1answer
90 views

Induction on all polynomial runtimes?

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

Term for a set that is not immune

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

Is there a notion of “sequential” idempotence?

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

tree decomposition elimination ordering

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?
2
votes
2answers
189 views

If $P=BPP$, then Is it correct that $IP=NP$?

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, ...
6
votes
2answers
217 views

Constraints on sliding windows

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

Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

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

Time Complexity of STCONN in One-Tape Turing Machine

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

Complexity of finding the largest induced subgraph with all even degrees

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 ...
9
votes
1answer
660 views

Relationship between two graph optimization problems

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

Is the decidability of a language decidable? [closed]

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

Scheduling and routing

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

How hard is it to approximate distance of linear code

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

Approximation quality of a simple linearization of binary quadratic program

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

What Is the Complexity of This Two-to-One Matching Problem?

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

Topologies for modelling divergence in the lambda-calculus

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 ...
1
vote
3answers
317 views

what is a model of computation, mathematically? [closed]

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

Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$

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(\...
2
votes
0answers
154 views

How do computers check if two functions are the same?

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

15 30 50 per page