All Questions

Filter by
Sorted by
Tagged with
-2
votes
0answers
27 views

Parameterized complexity of problems related to trees

I am trying to shown that Parameterized complexity of proper spanning tree. But i don't have any idea. Are there some problems related to spanning trees that are fixed parameterized intractability?
-1
votes
0answers
20 views

Steiner Tree Problem for circle graph

Can Steiner Tree Problem be solved in polynomial time on circle graph?
5
votes
1answer
129 views

Lower bound for the OR problem

Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
-1
votes
0answers
13 views

Understanding the behavior of Conflict Serializability and View Serializability with respect to blind writes

I have seen that most standard college textbooks of Database Management Systems use this method to classify whether a schedule is view serializable or not. I know the definitions of Conflict ...
3
votes
1answer
117 views

Does a graph resulting from the union of triangles has a particular name?

I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$. The union of both graphs ...
0
votes
0answers
57 views

Using the probabilistic method to fill the gaps in a proof of set disjointness

In the 2-party $k$-sparse set disjointness problem, we have a set $U$ of size $n$ and there are two parties: Alice, who gets a set $X \subseteq U$ and Bob who gets a string $Y \subseteq U$, and it ...
11
votes
7answers
17k views

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
0
votes
0answers
23 views

Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph. It seems like these problems would fall under the framework of network design problems (...
-1
votes
0answers
53 views

The parameterized complexity of proper edge-colored spanning tree

I want to FPT reduce from Multicolored Clique to proper edge-colored spanning tree, parameterized by treewidth. The input of Multicolored Clique consists of a graph $G$, an integer $k$, and a ...
1
vote
0answers
45 views

What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?

Suppose we have a graph $G$ with treewidth $t$. Let $p \in (0,1)$ be a constant. Then let's independently remove each edge from $G$ with probability $p$. What is the expected treewidth of the ...
11
votes
1answer
1k views

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
38
votes
2answers
2k views

Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time. You can do $O(n \...
8
votes
0answers
139 views

Can exponential-size depth-2 $CC^0[m]$ circuits with generalized $MOD_m$ gates compute arbitrary functions from $Z/mZ$ to $Z/2Z$?

Terminology $CC^0[m]$ is the set of polynomial-sized, constant depth circuits consisting entirely of $MOD_m$ gates for some $m \geq 2$, where a $MOD_m$ gate outputs a 1 if and only if the sum of its ...
4
votes
1answer
98 views

star height of star-free languages

I'm interested in the (restricted) star-height of star free-languages. Recalling the definitions: the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is $0$ if $\mathtt{e}= \...
0
votes
0answers
43 views

k-Median Problem With Restricted Centers

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 ...
1
vote
1answer
94 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 ...
-3
votes
0answers
41 views

Permutation Graphs is Chordal?

Whether the permutation graphs are a subclass of the chordal graphs? If not, what is the counter-example?
9
votes
0answers
113 views

Complexity of NFA to DFA minimization with binary threshold

What is the complexity of the following problem? Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$? ...
3
votes
0answers
137 views

Any problems for which we know the complexity, but no algorithms with the same time?

I suddenly found myself wondering if there are any problems for which the complexity (time or space or anything else) is proven, say to be O(n^2), but for which the best known algorithms are worse ...
-3
votes
0answers
36 views

Asymptotic Analysis of code that are unusual [closed]

We all know that the RUN Time of most of our program are Big O of linear time, quadratic time, cubic time or log time. But Can this be in unusual or uncommon poly time like $x^6-y$ or cosine function ...
2
votes
0answers
95 views

Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover

Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
1
vote
1answer
97 views

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$? I read abstract of this paper that mentioned an algorithm with running ...
-2
votes
0answers
66 views

Example of any non-NP decision problem without invoking time-hierarchy theorem

References appreciated for any problem decided by a Turing machine with a finite transition table that does not belong to the class NP. The non-membership is proven without the use of diagonalization ...
2
votes
2answers
92 views

Can finite difference methods approximate the space/time complexity of given programs?

While benchmarking a language prototype, I realized that I had a superlinear implementation of a test program, but wasn't sure if it was quadratic or cubic. I stayed up too late and wrote half a page ...
-1
votes
2answers
238 views

Partition a graph into two clusters

Suppose given a complete weighted graph $G=(V,E)$, with positive weight. Are there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized? ...
2
votes
1answer
95 views

exact path cover for undirected graph

In a Python plotting application, I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path. The number of ...
3
votes
1answer
91 views

Regular Expressions that converts into unambiguous automata

Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
-2
votes
0answers
19 views

algebraic specification online course, do you know any?

I am in need of an online course/tutorial on algebraic specification. Do you know any good resource with problems with solutions?
0
votes
1answer
104 views

Derandomizing arbitrary width *read-many* and *ordered* branching programs?

Modifying following TedP We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
9
votes
1answer
123 views

Oracle-Decidability of Algebraic Independence

Consider numbers $x_1,...,x_n\in \mathbb{R}$ given by TMs $M_1,...,M_n$ such that $M_i$ approximates $x_i$ to an arbitrary precision (by allowing it to run longer and longer). I am interested in the ...
-8
votes
0answers
63 views

Does this sequence of quantified boolean formulas make sense to anyone else? most of these qbfs are valid [closed]

do all logicians on earth know that a question is a qbf? yes and they know the answer to a qbf is always yes or no? yes ok good all logicians know that solving one qbf is hard and buggy? yes but ...
0
votes
1answer
118 views

Finding top-K items in a sliding window

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
5
votes
0answers
71 views

Fine-Grained Hardness for Undirected Hamiltonicity

The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time. However, for undirected graphs on $n$ nodes, there is an ...
2
votes
2answers
106 views

Status of certain problems in knot theory

I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
6
votes
1answer
258 views

Cook inspiration for NP completeness

An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for ...
0
votes
0answers
28 views

Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
1
vote
0answers
96 views

Does any physical process constitute a "computation"? [closed]

I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually ...
1
vote
0answers
51 views

Canonical tester for dense graphs: from tester to removal lemma?

A theorem of Goldreich and Trevisan [1] on property testing in the dense graph model states the following (docusing on the one-sided part): Suppose there exists a one-sided testing graph algorithm ...
1
vote
1answer
155 views

State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia: The polynomial-time approximation algorithm for Max-Cut with the best known ...
3
votes
1answer
219 views

Distinguishing permanent from false value

We are given a matrix $M$ with $0/1$ entries and the matrix is square of $n$ dimensions. We are given two integers $a$ and $b$ with promise one of the values is the permanent. Is there a faster than $...
1
vote
1answer
88 views

Maximally Permissive Strategies for Safety Properties

Different definitions of maximally permissive strategies exist. For instance, in (Bernet, Janin, and Walukiewicz 2002), strategies are compared by looking at inclusion of the behaviors/outcomes they ...
1
vote
1answer
51 views

Maximize the absolute value of connected nodes after $k$ modifications

Given a graph $G=\{V,E\}$, each node $i$ has a value $v_i$. Given budget $k$, we have $k$ chance to add 1 or minus 1 for a node's value, for example, $v'_i=v_i+1$ or $v'_i=v_i-1$. In particular, $v'_i$...
15
votes
4answers
2k views

What would be the consequences of PH=PSPACE?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing ...
7
votes
2answers
132 views

Algebraic characterisation of star-free safety languages

It is known that star-free languages are definable by aperiodic syntactic monoids. But is there any algebraic characterisation of star-free safety $\omega$-languages? Edit: A language $L$ is safety if ...
31
votes
4answers
4k views

Consequences of NP=PSPACE

What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones. In particular, would it have any ...
4
votes
1answer
259 views

Pagerank in directed *acyclic* graphs (DAG)

I deal with pagerank computations on large directed acyclic graphs (DAG). I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
2
votes
0answers
75 views

On-line pagerank in a streaming DAG (Directed Acyclic Graph)

Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
2
votes
1answer
72 views

Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight subset $S \...
2
votes
2answers
286 views

Some issues with proof of Fundamental Theorem of Statistical learning

I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...
1
vote
1answer
112 views

Divide and Conquer Algorithm for 1-Median Problem

Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the ...

15 30 50 per page
1
2 3 4 5
231