Sparse selfreducible sets and nonuniform lower bounds
type: Item
instance of: scholarly article
title: Sparse selfreducible sets and nonuniform lower bounds
zbMATH Open document ID: 1412.68079
author: Harry Buhrman
author: Leen Torenvliet
author: Falk Unger
author: Nikolai K. Vereshchagin
published in: Algorithmica
publication date: 2019-01-11T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/27793
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7000183
zbMATH Keywords: computational complexity
zbMATH Keywords: sparseness
zbMATH Keywords: selfreducibility
MaRDI profile type: Publication
OpenAlex ID: W2809558868
cites work: Quasi-linear truth-table reductions to \(p\)-selective sets
cites work: Q4039803
cites work: Q4258566
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Approximable sets
cites work: \(p\)-selective self-reducible sets: a new characterization of P
cites work: Mathematical Foundations of Computer Science 2005
cites work: On self-reducibility and weak P-selectivity
cites work: On Circuit-Size Complexity and the Low Hierarchy in NP
cites work: Self-reducible sets of small density
cites work: Separating classes in the exponential-time hierarchy from classes in PH
cites work: Polynomial-Time Membership Comparable Sets
cites work: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
cites work: Q4298260
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
cites work: Pseudorandomness for approximate counting and sampling
cites work: Relativized circuit complexity
DOI: 10.1007/S00453-018-0439-0
Recommended article: Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
Recommended article: On the sparse set conjecture for sets with low density
Recommended article: Q3809788
Recommended article: Reducibilities on tally and sparse sets
Recommended article: Sparse Sets, Lowness and Highness
Recommended article: On Sparse Complete Sets
Recommended article: Monotonous and randomized reductions to sparse sets
Recommended article: On the existence of hard sparse sets under weak reductions
Recommended article: Sparse sets and collapse of complexity classes
Recommended article: Q3830530
description: scientific article; zbMATH DE number 7000183