NP-hardness of approximating meta-complexity: a cryptographic approach (Q6499285)

scientific article; zbMATH DE number 7844654

Language	Label	Description	Also known as
default for all languages	No label defined
English	NP-hardness of approximating meta-complexity: a cryptographic approach	scientific article; zbMATH DE number 7844654

Statements

instance of

scholarly article

0 references

title

NP-hardness of approximating meta-complexity: a cryptographic approach (English)

0 references

0 references

0 references

0 references

8 May 2024

0 references

zbMATH Keywords

minimum circuit size problem

0 references

NP-hardness

0 references

cryptography

0 references

meta-complexity

0 references

witness encryption

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

$\Sigma_ 1^ 1$-formulae on finite structures

0 references

Minimum propositional proof length is NP-hard to linearly approximate

0 references

Q4474202

0 references

The Complexity of Complexity

0 references

Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

0 references

Power from Random Strings

0 references

Zero knowledge and circuit minimization

0 references

Minimum circuit size, graph isomorphism, and related problems

0 references

Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table

0 references

New insights on the (non-)hardness of circuit minimization and related problems

0 references

The minimum oracle circuit size problem

0 references

The non-hardness of approximating circuit size

0 references

Proof verification and the hardness of approximation problems

0 references

Probabilistic checking of proofs

0 references

$BPP$ has subexponential time simulations unless $EXPTIME$ has publishable proofs

0 references

On the (im)possibility of obfuscating programs

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$

0 references

Secret-Sharing Schemes: A Survey

0 references

On Worst‐Case to Average‐Case Reductions for NP Problems

0 references

Identity-Based Encryption from the Weil Pairing

0 references

Q4432349

0 references

Tighter connections between derandomization and circuit lower bounds

0 references

New directions in cryptography

0 references

On the hardness of approximating label-cover

0 references

Analytical approach to parallel repetition

0 references

A threshold of ln <i>n</i> for approximating set cover

0 references

Random-Self-Reducibility of Complete Sets

0 references

Hardness of approximate two-level logic minimization and PAC learning with membership queries

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

Candidate Multilinear Maps from Ideal Lattices

0 references

Candidate indistinguishability obfuscation and functional encryption for all circuits

0 references

Witness encryption and its applications

0 references

On the Cryptographic Applications of Random Functions (Extended Abstract)

0 references

Probabilistic encryption

0 references

A Pseudorandom Generator from any One-way Function

0 references

Unexpected hardness results for Kolmogorov complexity under uniform reductions

0 references

Q5121893

0 references

On the average-case complexity of MCSP and its variants

0 references

Limits of minimum circuit size problem as oracle

0 references

On the NP-Completeness of the Minimum Circuit Size Problem.

0 references

Q5875732

0 references

Q5092472

0 references

Q5121895

0 references

Indistinguishability obfuscation from simple-to-state hard problems: new assumptions, new techniques, and simplification

0 references

Indistinguishability obfuscation from LPN over $\mathbb{F}_p$, DLIN, and PRGs in $NC^0$

0 references

Circuit minimization problem

0 references

Reducibility among combinatorial problems

0 references

Q3549718

0 references

On the notion of infinite pseudorandom sequences

0 references

On the Complexity of Learning Minimum Time-Bounded Turing Machines

0 references

Three approaches to the quantitative definition of information<sup>*</sup>

0 references

One-Way Functions and (Im)perfect Obfuscation

0 references

Secret-sharing for NP

0 references

Q4071737

0 references

Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity

0 references

On the possibility of basing cryptography on $\mathsf{EXP}\ne \mathsf{BPP} $

0 references

Computationally Sound Proofs

0 references

On the (non) $\mathsf{NP}$-hardness of computing circuit complexity

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

Natural proofs

0 references

Hardness of KT characterizes parallel cryptography

0 references

Discrete logarithm and minimum circuit size

0 references

Fuzzy Identity-Based Encryption

0 references

Circuit lower bounds from NP-hardness of MCSP under turing reductions

0 references

How to share a secret

0 references

Identity-based cryptosystems and signature schemes

0 references

A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms

0 references

Pseudorandomness and average-case complexity via uniform reductions

0 references

Witness encryption and null-iO from evasive LWE

0 references

Identifiers

DOI

10.1145/3564246.3585154

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6499285