Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WITNESS ENCRYPTION:
Reports tagged with Witness Encryption:
TR23-046 | 13th April 2023
Yizhi Huang, Rahul Ilango, Hanlin Ren

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with ... more >>>


TR23-206 | 9th December 2023
Yilei Chen, Jiatu Li

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

Revisions: 1

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... more >>>




ISSN 1433-8092 | Imprint