Local reduction (Q1641001)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Local reduction	scientific article

Statements

scholarly article

0 references

Local reduction (English)

0 references

Hamidreza Jahanjou

0 references

0 references

0 references

Information and Computation

0 references

publication date

14 June 2018

0 references

zbMATH Keywords

computational complexity

0 references

Cook-Levin

0 references

reductions

0 references

ACC0

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.ic.2018.02.009

0 references

Two-Tape Simulation of Multitape Turing Machines

0 references

Satisfiability Is Quasilinear Complete in NQL

0 references

Relations Among Complexity Measures

0 references

Short propositional formulas represent nondeterministic computations

0 references

0 references

On O(Tlog T) reduction from RAM computations to satisfiability

0 references

Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries

0 references

Fast reductions from RAMs to delegatable succinct constraint satisfaction problems

0 references

Reducing the complexity of reductions

0 references

Towards a Study of Low-Complexity Graphs

0 references

Time-space lower bounds for satisfiability

0 references

A Survey of Lower Bounds for Satisfiability and Related Problems

0 references

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

0 references

Natural Proofs versus Derandomization

0 references

Amplifying lower bounds by means of self-reducibility

0 references

3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General

0 references

0 references

A Boolean function requiring 3n network size

0 references

Explicit lower bound of <i>4.5n - o(n)</i> for boolena circuits

0 references

0 references

0 references

0 references

On the power of small-depth threshold circuits

0 references

On the complexity of \(k\)-SAT

0 references

A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

0 references

An improved exponential-time algorithm for <i>k</i> -SAT

0 references

Threshold circuits of bounded depth

0 references

Majority gates vs. general weighted threshold gates

0 references

On uniform circuit complexity

0 references

New algorithms and lower bounds for circuits with linear threshold gates

0 references

Short PCPs with Projection Queries

0 references

Derandomizing the HSSW algorithm for 3-SAT

0 references

A 5n − o(n) Lower Bound on the Circuit Size over U 2 of a Linear Boolean Function

0 references

Size--Depth Tradeoffs for Threshold Circuits

0 references

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

0 references

Nearly-linear size holographic proofs

0 references

Searching for Primitive Roots in Finite Fields

0 references

A hierarchy for nondeterministic time complexity

0 references

Separating Nondeterministic Time Complexity Classes

0 references

A Turing machine time hierarchy

0 references

On the Power of Small-Depth Computation

0 references

Identifiers

zbMATH Open document ID

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

10.1016/J.IC.2018.02.009

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1641001

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q1641001&oldid=38677819"