# All Questions

11,357 questions
Filter by
Sorted by
Tagged with
4 views

### Proving that a given formula in LTL is the smallest way to express it

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

### Given two languages and their grammars can you translate from one to the 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. ...
24 views

### Scheduling algorithms with weighted tasks

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

### Is there a regular bipartite graph where the minimum cuts are trivial?

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

### Is there any Bi-criteria PTAS for Metric $k$-Median?

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

### end node with unique path length from the start node in a DAG [closed]

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$ ...
55 views

### Does every graph of clique-width 3 have a large induced subgraph of clique-width 2?

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

### How to think about comp in cubical type theory

Consider the definition: ...
70 views

### External failure of law of excluded middle in Martin-Löf type theory

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?
40 views

### 3-hitting set iterative compression

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

### Claw-free graph linear kernel [closed]

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

### Is the difference between the acyclic chromatic number and the star chromatic number unbounded?

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

### Sublinear Time Regular Expression Search

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 ...
166 views
+50

### How is a “low-degree polynomial” precisely defined in Algebrization?

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

### Does the Linz Ĥ halt when applied to its own TM description? [closed]

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? ...
106 views

### Why A.I. is better than humans at chess but not at mathematics [closed]

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 (...
38 views

...
131 views

### Triangle detection hardness in regular graphs

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

### Complete problems for $(NP\cap CoNP)/poly$ class and universal representations

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

### Why most of the top TCS conferences are not double-blind?

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

### What kind of procedure is used to calculate the thread

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

### Example use cases for induction-recursion

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&...
33 views

### Full version of the paper “Characterization of Temporal Property Classes”

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

### Are there two definitions of Cobham's thesis?

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

### Randomized algorithm for finding Minimum feedback vertex set

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

### Adjusting the loss function for Support Vector Machines for SVC in sklearn

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

### CubicalTT: successor of add proof?

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

### What does width $4$ permutation branching program correspond to?

$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 ...
168 views

### Simultaneous evidence for $L\neq NL$ and $P\neq NP$

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

### What conditions are necessary (and sufficient) for the order-dual of a Scott-Ershov domain to also be a domain?

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

### Find research partner (profession and beginner)

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

### Has this notion of connectivity in edge-colored graphs been studied?

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

### What is the polynomial representation of the Hamming weight function?

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

### Translation of Counter-free automata into Linear Temporal Logic

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