All Questions

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

How to think about `comp` in cubical type theory

Consider the definition: ...
2
votes
1answer
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?
-2
votes
0answers
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 ...
-3
votes
0answers
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 ...
2
votes
1answer
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 ...
9
votes
2answers
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 ...
7
votes
0answers
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 ...
-4
votes
0answers
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? ...
-3
votes
0answers
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 (...
-4
votes
0answers
38 views
1
vote
0answers
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 ...
3
votes
0answers
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 ...
12
votes
1answer
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 ...
-3
votes
0answers
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. ...
2
votes
1answer
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&...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
-4
votes
0answers
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 ...
-1
votes
0answers
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 - ...
0
votes
0answers
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): ...
4
votes
0answers
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 ...
2
votes
0answers
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$?
3
votes
0answers
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 ...
-1
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
1
vote
2answers
152 views

Finding the point that maximizes a linear function

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

Example of an context-sensitive language with a specific number of words of length $n$

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

Epsilon-closure and DFA minimization algorithms for probabilistic NFA

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

Resource for Understanding this Notation [closed]

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

Do there exist two equivalent objective functions one of which can be approximated but another one cannot?

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

Finding uniformly random perfect matching of a graph

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

Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$

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

“Fast” approximation algorithm for geometric hitting set of same-height rectangles

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

Reference request: An algebraic characterisation of LTL[XF]-definable word languages

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

Can the rendezvous problem be solved without exploration in synchronous rings?

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

Renaming this forum [migrated]

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

Do such instances always admit a 3D matching?

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 ...
1
vote
0answers
62 views

MLTT/MiniTT: why do normal forms of sum types carry environments?

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

What are the pros and cons for type cases in dependent type theories?

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 ...
1
vote
1answer
68 views

Generalization bound for parameters rather than loss functions

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

Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

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

15 30 50 per page
1
2 3 4 5
228