Local restrictions from the Furst-Saxe-Sipser paper

DOI10.1007/s00224-016-9730-0zbMath1362.68113OpenAlexW2557257622MaRDI QIDQ519884

Suguru Tamaki, Osamu Watanabe

Publication date: 31 March 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100767956

zbMATH Keywords

random restrictionalgorithm designcomputational complexity theorylocal restriction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• The isomorphism conjecture for constant depth reductions
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On one-one polynomial time equivalence relations
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Constant depth circuits, Fourier transform, and learnability
• Parity, circuits, and the polynomial-time hierarchy
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Analysis of Boolean Functions
• Reducing the complexity of reductions