Skip to main content

Questions tagged [fine-grained]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
1 answer
427 views

Relation between ACC^0 and DTIME

In a breakthrough Ryan Williams (STOC13/14) showed that $\mathsf{NEXP} \nsubseteq \text{non-uniform } \mathsf{ACC}^0$. How far can we potentially push this result? In other words, what is the largest $...
Nicholas Brandt's user avatar
10 votes
0 answers
160 views

Fine-grained complexity for game-type problems

My specific question is the following. Consider the following problem that I call Strange-TQBF: there is a Boolean function $f(x_1, \ldots, x_n)$ and two players Alice and Bob. They take turns ...
Alexey Milovanov's user avatar
4 votes
0 answers
98 views

Time Complexity of Pairwise Graph Connectedness

The Setup Consider the following algorithmic problem which, for now, I will call $\mathsf{2GraphConnector}$. Input: A natural number $|V|$, and a finite collection $\mathscr{E} = \left\{E_1, E_2, \...
k-variant's user avatar
3 votes
0 answers
198 views

Barriers and ETH, or its variants

ETH (Exponential Time Hypothesis) or its variants SETH(Strong ETH), NSETH(Non Deterministic SETH) haven't been resolved as yet. But resolution to any of the above hypotheses could lead to interesting ...
user3483902's user avatar
  • 1,261
6 votes
1 answer
348 views

Lower-bounds under SETH

After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are ...
Jova's user avatar
  • 161
6 votes
1 answer
357 views

Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP (Floyd-Warshall, Bellman-Ford, Johnson's) work with the standard definition of the ...
Koen's user avatar
  • 61
5 votes
0 answers
105 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 ...
Naysh's user avatar
  • 686
8 votes
0 answers
170 views

Is APSP verification easier than APSP?

In APSP, the input is an $n$-node directed weighted graph $G$, and the output is an $n \times n$ matrix holding pairwise shortest path distances between nodes in $G$. Define "APSP-Verification" as ...
GMB's user avatar
  • 2,403
16 votes
0 answers
279 views

Does small circuits for a NP-complete problem contradict ETH?

The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
Jacobs's user avatar
  • 161
13 votes
1 answer
560 views

The problem of deciding whether a monotone CNF implies a monotone DNF

Consider the following decision problem Input: A monotone CNF $\Phi$ and a monotone DNF $\Psi$. Question: Is $\Phi \to \Psi$ a tautology? Definitely you can solve this problem in $O(2^n \cdot \...
Sasha Kozachinskiy's user avatar
2 votes
0 answers
219 views

Approximating the Radius of a (Dense) Graph

For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius. A $(1+\epsilon)$-approximating of APSP for a ...
Mohemnist's user avatar
  • 230
5 votes
1 answer
157 views

Reference request: complexity of $k$-partite $k$-SAT

Let's consider following variation of $k$-SAT that I will call $k$-partite $k$-SAT: given $n$ variables that are divided into $k$ groups and a $k$-SAT formula $\phi$ such that each clause has literal ...
ivmihajlin's user avatar
8 votes
0 answers
296 views

Given a Boolean formula, does there exist a small circuit that computes a satisfying assignment?

The 3-SAT problem can be defined as follows: 3-SAT Input: A 3-CNF formula $\phi$ of size $m$ with $n$ variables. Question: Does there exist a variable assignment that satisfies $\phi$? ...
Michael Wehar's user avatar
5 votes
1 answer
247 views

Hardness of Subgraph isomorphism problem for sparse pattern graph

Subgraph isomorphism problem is a well studied problem: given graphs $G$ and $H$, one needs to answer if $H$ contains $G$ as a subgraph. It was proven that this problem requires $|H|^{\theta(|G|)}$ ...
ivmihajlin's user avatar
4 votes
1 answer
167 views

Algorithms in preprocessed universe [closed]

In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe. They were able to provide an ...
ivmihajlin's user avatar
5 votes
0 answers
151 views

Online triangle counting

Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs. Given a graph $G$ and a collection $C$ of subsets of ...
ivmihajlin's user avatar
7 votes
1 answer
1k views

On reducing the hardness of CNF-SAT to k-Clique

CNF-SAT refers to the following problem: Given a boolean formula $\phi$ in conjunctive normal form, does there exist an assignment to the variables that satisfies $\phi$. There are several ...
Michael Wehar's user avatar
8 votes
1 answer
329 views

Two DFA intersection emptiness connections to SETH & L vs P

(re "fine grained complexity") Wehar has proved that Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false. does anyone see any particular key proof difficulty, challenge, ...
vzn's user avatar
  • 11.1k
14 votes
0 answers
691 views

Does solving matrix multiplication in quadratic time imply that SETH is false?

I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time. In other words, ...
Michael Wehar's user avatar
25 votes
3 answers
1k views

What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" ...
user avatar