All Questions

Filter by
Sorted by
Tagged with
3
votes
2answers
171 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 ...
0
votes
1answer
112 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 ...
5
votes
1answer
120 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, ...
5
votes
0answers
83 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 ...
3
votes
0answers
103 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$ ...
0
votes
0answers
35 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
104 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
56 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
54 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$...
2
votes
0answers
91 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 ...
7
votes
2answers
144 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 ...
-1
votes
1answer
88 views

Non-(PAC)-Learnable Classes

I'm learning about PAC-learnability. I've figured out how to show that a class of classifiers is PAC-learnable, but what about if I want to show that a class of classifiers is not PAC-learnable? How ...
2
votes
1answer
145 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 ...
1
vote
1answer
173 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 ...
0
votes
0answers
49 views

Minimal lexicographical path on DAG in O(||V| + |E|)

Let's assume, that we have directed asyclic graph and nodes U and V. Every edge of this graph is marked with alphabet letter (alphabet size is fixed). Is there any way to answer, what is the shortest ...
7
votes
1answer
291 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 ...
3
votes
1answer
72 views

Encapsulation of OOP and referential transparency of functional programming

I would like to understand more about the 'orthogonality' of OOP and functional programming. What makes me confused is the 'encapsulation' of OOP and 'referential transparency of functional ...
7
votes
0answers
115 views

Halting problem for finitary PCF

Is the halting problem decidable for finitary PCF? By "halting problem" I mean the problem of deciding whether a closed PCF term evaluates to bottom under the denotational semantics of PCF. ...
0
votes
0answers
50 views

Finding the best $k-$subset which maximizes a matrix sum

Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem: Is there a polynomial-time solution to the following ...
0
votes
0answers
75 views

Large CLIQUE approximation

I am interested in algorithms to identify large cliques in graphs where the largest clique is a large fraction (definitely greater than half, perhaps as great as 4/5) of the total number of vertices. ...
2
votes
1answer
99 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 \...
4
votes
1answer
186 views

Upper bound on the expected number of correct bits via a "lossy compression"

Consider the following "compression problem" for a pair $(C,D)$ of algorithms: $C$ receives a uniformly random $x \in \{0,1\}^n$ and outputs a smaller bit string $y \in \{0,1\}^s$. Algorithm ...
1
vote
1answer
197 views

Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several ...
10
votes
1answer
190 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 ...
5
votes
0answers
91 views

Why is the ellipsoid method numerically unstable?

In the Ellipsoid method wikipedia entry under the performance section, it is mentioned that the Ellipsoid method often times is numerically unstable in practice: "On even "small"-sized ...
1
vote
1answer
147 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 ...
0
votes
0answers
37 views

Is it possible to count the total number of local minima for a scalar, multivariate function?

We can assume the function is differentiable, but it is also non-convex and setting the gradient equal to zero has no analytical solution. We can also assume that the domain is bounded, namely the ...
1
vote
0answers
50 views

Decision tree vs. pebble game lower bounds

This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
3
votes
0answers
74 views

Exact FPT Algorithm for Continuous Euclidean $k$-Means

The continuous Euclidean $k$-means problem is defined as follows: Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ ...
0
votes
0answers
22 views

Fast algorithms for convex-convex quadratic fractional programming

What are the fastest algorithm(s) (possibly approximation algorithms) for solving convex-convex quadratic fractional programming problems, i.e. optimization problems of the form $$ \begin{align*} \sup&...
2
votes
2answers
116 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
0answers
134 views

$\mathbf{AC}^0$ lower bounds for $\mathsf{Gap}\text{-}\mathsf{Max3SAT}$

Various gapped maximization problems are known not to be $\mathbf{NP}$-hard under $\mathbf{AC}^0$ reductions, e.g., $\mathsf{Gap}_{1,\epsilon}\text{-}\mathsf{Max3SAT}$ (see, e.g., Proposition 4 of ...
3
votes
2answers
205 views

How does axiom K contradict univalence?

I have seen it claimed several times that axiom K is inconsistent with univalence (e.g. here and here), but I have never seen a proof sketch. Specifically, I'm curious about how this manifests in the ...
1
vote
0answers
94 views

Is Kotlin's type system Turing complete?

Java's type system is Turing complete. For whatever reason, I was under the impression that Kotlin's type system (for concreteness, let's say the latest version of the language -- ...
0
votes
1answer
98 views

Diophantine equations with bounds on variables

Solving Diophantine equations is famously known to be undecidable. What about Diophantine equations to be solved over a finite domain? In particular, if I put an upper bound $k$ over the value of the ...
1
vote
1answer
61 views

Non-random errors with a Reed Solomon code

If I have a RS code, say [46, 16, 31], then I have a guaranteed error correction up to 15 symbols. I have no idea if it matters, but the code I have in front of me ...
0
votes
0answers
59 views

EXPSPACE-complete problems involving numbers

This is a subset of this question. I'm looking for EXPSPACE-complete problems, for using in a reduction, which involve numbers in some ways, since my target problem involves numbers and linear ...
-1
votes
1answer
66 views

Is there a fundamental link between Nash's equilibrium and Turing's halting problem?

Since Nash equilibrium exists, is there a computational analogue of this equilibrium point? I am trying to approach Nash equilibrium from computational point of view to see if the equilibrium point ...
1
vote
1answer
74 views

partitioning points in the plane into two clusters to minimize maximum cluster diameter

What is a fast algorithm for the following problem? input: a set of $n$ pairs of points in the Euclidean plane output: a partition of the points into two clusters so that, for each given pair, the ...
0
votes
0answers
75 views

Low-Treewidth Sorting Networks

It was previously asked if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}_n$ on $n$ inputs. While a construction using online algorithms and the ...
-1
votes
1answer
63 views

Is function composition associative in non-pure programming languages?

We know that function composition is associative in theoretical programming languages such as STλC, and pure functional programming languages such as Haskell. Is the same true for languages where ...
7
votes
3answers
945 views

Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?

I have attended a decent number of TCS conferences. It is good that researchers solve difficult problems. However, I am often interested in the reason why a problem is interesting in the first place. ...
-1
votes
1answer
87 views

Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

I understand the logic minimization problem is NP-hard when given the onset, since the last step is equivalent to set cover optimization. If instead we are given a partial truth table, and we just ...
4
votes
1answer
301 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 ...
1
vote
0answers
124 views

For what parameters is minimum distance hard?

It has been shown by Vardy that minimum distance of a code is NP-hard (see Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757--...
3
votes
1answer
578 views

Determinising unambiguous automata without exponential blowup

Is it possible to determinise unambiguous finite automata without exponential blowup in the number of states? I think it should not be possible but I am unable to come up with counterexamples.
2
votes
0answers
103 views

Asymptotic complexity lower bounds of proof checking

This paper on universal search mentions (on pp. 6-7) that proof checking can be done in $O(n^2)$ where $n$ is the length of the proof. Is this optimal? I don't want to specify the problem too ...
4
votes
1answer
129 views

Is Barbara Liskov's claim that CLU was the first implemented language to provide linguistic support for data abstraction accurate?

According to this paper by Barbara Liskov, CLU was "The first implemented programming language to provide direct linguistic support for data abstraction". She then defines "data ...
3
votes
1answer
157 views

complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
2
votes
1answer
92 views

Property testable in sublinear time in bounded degree graphs but not in general graphs

Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...

15 30 50 per page