All Questions

I am looking for a way to prove that a given LTL formula is expressed with the fewest number of temporal operators possible. I would like to do this to compare the expressive length with other ...

Often I use sed 's/match/replacement/' in places where I would rather have a more formal tool, just because sed is what I know. ...

I am working on a problem where you have tasks: $t_1, t_2, t_3,...$ with different weights $w_1, w_2, w_3,...$. The objective is to maximize the combined weight of the tasks that are finished before ...

My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial? We can ...

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...

Let $G(V,E)$ be a directed acyclic graph with all edge weights set to one and $s\in V$ be the start node, $E \in V\backslash s $ be the set of end nodes. My problem is to find an end node $e\in E$ ...

Is there a constant $\alpha>0$ such that every graph $G$ of clique-width $3$ and order $n$ has an induced subgraph of order at least $\alpha n$ and clique-width at most $2$ (in other words, the ...

Consider the definition: ...

Is there an explicit type $T$ in Martin-Löf type theory such that $(T\to \mathbf{0})\to\mathbf{0}$ has an explicit closed term and $T$ can be shown externally to not have closed terms?

I have a question which i tried to solve without success. I need to prove that if 3-Hitting Set can be solved in time $2^kn^{O(1)}$,then 4-Hitting Set can be solved in time $3^kn^{O(1)}$. There is a ...

I'm having a hard time solving the problem below: In Claw-free problem, we are given a graph G and $k$, and the objective is to decide whether there exists a subset S $\subseteq$ V (G) of size at most ...

Is $\chi_s(G)-\chi_a(G)$ unbounded in general graphs? I thought $\chi_s(G)-\chi_a(G)$, the difference between the star chromatic number and the acyclic chromatic number, is unbounded for general ...

Does there exist a data structure with the following properties. Given a string $s$, it performs some polynomial amount of precomputation to construct the data structure. After construction, it allows ...

I'm going through papers which present algebrization as a barrier and I'm trying to understand how "low-degree" polynomials are precisely defined, i.e. are they low with respect to the ...

The original version of this question: When Linz Ĥ is applied to its own TM description and Ĥ has an embedded simulating halt decider does this decider correctly decide that its input does not halt? ...

I apologize in advance if the question is too naive or not suitable for this website. There are many artificial intelligence programs whose performance in chess exceeds the best humans at chess (...

...

Consider a tripartite graph over $n^{1-\epsilon}$ vertices each in sets $I, J, K$. Suppose we impose a constraint that every vertex has degree $n^\epsilon/c$ for some constant $\epsilon > 0$ and ...

It is conjectured that $NP\cap CoNP$ does not have a complete problem with respect to the polynomial-time many-to-one reductions. I would like to know the current knowledge about the nonuniform ...

I have found that the most notable TCS conferences like FOCS, STOC, SODA, and ICALP are single-blind. That is the authors do not know the identity of reviewers; however, the reviewers know the ...

my question would be how can I see which method is used to distribute the computing time to the following threads. ...

I know of only two uses of induction-recursion: Encoding universes as a type, as shown in the Agda docs for recursion Encoding Finite sets as shown in Conor Mc'Bride's "datatypes of datatypes&...

Look at this paper: E. Chang, Z. Manna, A. Pnueli. "Characterization of Temporal Property Classes" The proof of Theorem 8 at page 8 says: "We will outline the proof which appears in the ...

In wikipedia, Cobham's thesis (or Cobham-Edmonds thesis) states: computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time So ...

Algorithm FVS(G, k): If k < 0, return ”NOT FOUND” If G is acyclic (i.e., a forest), return  While there exists a vertex 𝑢 of degree at most 2: If deg(u) = 1, remove u If deg(u) = 2, i.e. u's ...

I have the following problem. The minimization problem of the SVM that I want to solve is: $$ \min_{w, b} \frac{1}{2}w^{T}w + \sum^{m}_{i=1}C_{i}xi_{i} $$ Subject to: $$ y_{i}(w^{T}x_{i} - b) \geq 1 - ...

Lecture 2 of the cubical type theory lectures provide a proof of (suc a) + b = suc (a + b): ...

$L$ can be computed by a family of programs over $S_3$ of polynomial length if and only if $L$ can be computed by a family of $MOD3 ◦ MOD2$ circuits of polynomial size. $L$ can be computed by a family ...

We believe $L\neq NL$ and $P\neq NP$. Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?

That is, considering the underlying poset of a domain, when does the order-dual poset also comprise a domain? Below's a little, not strictly necessary, elaboration of that question. Usual ...

I've 10 years of industrial work, but in my free time, I do research, write papers to conferences, help to teach to my old friend at the university and I even did a Ph.D. full-time program. Now, I've ...

Consider a simple graph $G$ where each edge is either red or blue. I'm interested in the following notion of connectivity: Two vertices $u$ and $v$ are said to be connected if there is a path ...

For any function $f: \{1,-1\}^n \rightarrow \{1,-1\}$, there is a unique multilinear polynomial $p \in \mathbb{R}[x_1,\dots, x_n]$ for which $p(x)=f(x)$ for all $x \in \{1,-1\}^n$ (see e.g. Lemma 4.1 ...

There is a well-known equivalence between counter-free automata and Linear Temporal Logic (which is cited for example by [1]). However, I cannot find a concrete way to obtain an LTL formula from a ...

Consider $N$ two-dimensional points of the form $(x_i, y_i)$ where all $x_i, y_i > 0$ are positive integers. We will be given a workload of queries $Q = \{c_1, \dots, c_k\}$ where for each $c_j \in ...

Let $s_L(n)$ denote the number of words of length $n$ in $L$. For context-free languages it is known that $s_L(n)$ is either polynomial or exponential. For context-sensitive languages this is probably ...

Are there any algorithms performing e-closures and DFA minimizations for probabilistic Finite Automata? Given that probabilistic NFAs might have multiple accepting paths for generating equivalent ...

I am trying to read this paper: https://arxiv.org/abs/1510.00925. I am familiar with grammars, but I cannot understand the notations in figure 1. Can anyone suggest a resource or book where I can ...

I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...

Problem: Suppose that we have a graph $ G $ which admits at least one perfect matching. I would like to know if there is an algorithm that allows to find any perfect matching of this graph uniformly ...

For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not ...

In the Geometric Hitting Set problem, we are given a set of $m$ geometric objects and a set of $n$ points in $\mathbb{R}^2$, and we wish to find a small subset of the points that hits all the objects. ...

I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1). A similar ...

Problem Definitions: Rendezvous: A number of agents, in this case two, that start from distinct nodes of a ring need to meet in some node that is not known in advance. (Collaborative) Exploration: A ...

Following the number of off-topic questions, maybe we should consider renaming this forum? Perhaps something like: "Research topics in computer science" or alike.

I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching. We are given 3 sets $A,B,C$ containing $m$ elements ...

I am learning how to implement MiniTT: a simple type theoretic language, which is a dependently typed language with sum types, mutual recursive/inductive definitions and a universe of small types. A ...

Pattern matching on $\cal U$ is allowed in XTT and Idris2 (for unerased types), and that implies the injectivity of type constructors (that's just my intuition, though -- I also wonder how do I prove ...

I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and ...

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...