Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FINE-GRAINED COMPLEXITY:
Reports tagged with fine-grained complexity:
TR15-148 | 9th September 2015
Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

We introduce the Nondeterministic Strong Exponential Time Hypothesis
(NSETH) as a natural extension of the Strong Exponential Time
Hypothesis (SETH). We show that both refuting and proving
NSETH would have interesting consequences.

In particular we show that disproving NSETH would ... more >>>


TR17-130 | 30th August 2017
Oded Goldreich, Guy Rothblum

Worst-case to Average-case reductions for subclasses of P

Revisions: 4

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.
These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.
more >>>


TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>


TR18-210 | 30th November 2018
Karthik C. S., Pasin Manurangsi

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>


TR19-054 | 9th April 2019
Joshua Brakensiek, Venkatesan Guruswami

Bridging between 0/1 and Linear Programming via Random Walks

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial ... more >>>


TR19-125 | 27th August 2019
Elazar Goldenberg, Karthik C. S.

Hardness Amplification of Optimization Problems

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.

We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance ... more >>>


TR19-135 | 2nd October 2019
Michel Goemans, Shafi Goldwasser, Dhiraj Holden

Doubly-Efficient Pseudo-Deterministic Proofs

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>


TR20-177 | 12th October 2020
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

Counting Subgraphs in Degenerate Graphs

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>


TR21-156 | 10th November 2021
Boris Bukh, Karthik C. S., Bhargav Narayanan

Applications of Random Algebraic Constructions to Hardness of Approximation

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural.

(*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in ... more >>>


TR21-157 | 2nd November 2021
Monika Henzinger, Andrea Lincoln, Barna Saha

The Complexity of Average-Case Dynamic Subgraph Counting

Statistics of small subgraph counts such as triangles, four-cycles, and $s$-$t$ paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most ... more >>>


TR21-165 | 21st November 2021
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Revisions: 1

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability $1$, and rejects invalid proofs with probability arbitrarily close to $1$. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>


TR22-170 | 15th November 2022
Huck Bennett

The Complexity of the Shortest Vector Problem

Revisions: 1

Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the ... more >>>


TR23-082 | 1st June 2023
Ryan Williams

Self-Improvement for Circuit-Analysis Problems

Revisions: 1

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a ``self-improving'' (or ``bootstrapping'') theorem for Circuit-SAT, $\#$Circuit-SAT, and its fully-quantified version: solving one of these problems faster for ``large'' circuit sizes implies a significant speed-up for ``smaller'' circuit ... more >>>


TR23-171 | 15th November 2023
Shuichi Hirahara, Rahul Ilango, Ryan Williams

Beating Brute Force for Compression Problems

A compression problem is defined with respect to an efficient encoding function $f$; given a string $x$, our task is to find the shortest $y$ such that $f(y) = x$. The obvious brute-force algorithm for solving this compression task on $n$-bit strings runs in time $O(2^{\ell} \cdot t(n))$, where $\ell$ ... more >>>


TR24-142 | 17th September 2024
Ryan Williams

The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the non-existence of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggest a potential ... more >>>




ISSN 1433-8092 | Imprint