Awesome Computational Complexity

Explicit Separations for One-Query Unitary Synthesis (2026)

Fangqi Dong et al.

4.75

A Five-Plane Reference Architecture for Runtime Governance of Production AI Agents (2026)

Krti Tallam

1.89

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms (2026)

Alessandro Epasto et al.

1.67

Privately Estimating Black-Box Statistics (2025)

G\"unter F. Steinke et al.

1.44

Cryptographic Conditions for Efficient Testing of Distributions and Quantum States (2025)

Bruno Cavalar et al.

1.44

Efficient derandomization of differentially private counting queries (2025)

Surendra Ghentiyala

1.44

Improved Quantum Lifting by Coherent Measure-and-Reprogram (2025)

Alexandru Cojocaru et al.

1.39

NISQ Security and Complexity via Simple Classical Reasoning (2025)

Alexandru Cojocaru et al.

1.39

Immutability Does Not Guarantee Trust: A Formal and Logical Refutation (2025)

Craig S Wright

1.28

Black-Box Crypto is Useless for Pseudorandom Codes (2025)

Sanjam Garg et al.

1.22

Leakage-Resilient Extractors against Number-on-Forehead Protocols (2025)

Eshan Chattopadhyay et al.

1.22

Safety Analysis in the NGAC Model (2025)

Brian Tan and Ewan S. D. Davies and Indrakshi Ray and Mahmoud A. Abdelgawad

1.17

Improved Round-by-round Soundness IOPs via Reed-Muller Codes (2025)

Dor Minzer and Kai Zhe Zheng

1.11

Parallel Kac's Walk Generates PRU (2025)

Chuhan Lu et al.

1.11

Quantum Lifting for Invertible Permutations and Ideal Ciphers (2025)

Alexandru Cojocaru et al.

1.11

Differentially Private Compression and the Sensitivity of LZ77 (2025)

Jeremiah Blocki et al.

1.00

Pseudorandom quantum authentication (2025)

Tobias Haug et al.

0.94

Experimental relativistic zero-knowledge proofs with unconditional security (2025)

Chen-Xun Weng et al.

0.94

Quantum randomized encoding, verification of quantum computing, no-cloning, and blind quantum computing (2020)

Tomoyuki Morimae

—

InstaHide's Sample Complexity When Mixing Two Private Images (2020)

Baihe Huang et al.

—

Lightweight Encryption for the Low Powered IoT Devices (2020)

Muhammad Usman

—

Quantum Pseudorandomness and Classical Complexity (2021)

William Kretschmer

—

Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation (2021)

Iftach Haitner et al.

—

Solving the Workflow Satisfiability Problem using General Purpose Solvers (2021)

Daniel Karapetyan and Gregory Gutin

—

Communication Complexity of Private Simultaneous Quantum Messages Protocols (2021)

Akinori Kawachi and Harumichi Nishimura

—

Valued Authorization Policy Existence Problem: Theory and Experiments (2021)

Jason Crampton et al.

—

Property-Preserving Hash Functions from Standard Assumptions (2021)

Nils Fleischhacker and Kasper Green Larsen and and Mark Simkin

—

A New Lever Function with Adequate Indeterminacy (2021)

Shenghui Su et al.

—

Compressed Oblivious Encoding for Homomorphically Encrypted Search (2021)

Seung Geol Choi et al.

—

Quantum Money from Quaternion Algebras (2021)

Daniel M. Kane et al.

—

The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs (2021)

Jeremiah Blocki and Blake Holman and Seunghoon Lee

—

Efficient and Secure TSA for the Tangle (2021)

Quentin Bramas (UNISTRA et al.

—

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR (2021)

Itai Dinur and Nathan Keller and Ohad Klein

—

An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm (2021)

Zongxia Li et al.

—

Efficient Quantum Voting with Information-Theoretic Security (2021)

Emil T. Khabiboulline et al.

—

Local inversion of maps: A new attack on Symmetric encryption, RSA and ECDLP (2022)

Virendra Sule

—

A Note on the Hardness of Problems from Cryptographic Group Actions (2022)

Giuseppe D'Alconzo

—

On the Conjugacy Search Problem in Extraspecial p-Groups (2022)

Simran Tinani

—

Verifiable Quantum Advantage without Structure (2022)

Takashi Yamakawa et al.

—

Indistinguishability Obfuscation of Circuits and its Application in Security (2022)

Shilun Li et al.

—

An Algebraic-Geometry Approach to Prime Factorization (2022)

Alberto Montina et al.

—

Computational indistinguishability and boson sampling (2022)

Georgios M. Nikolopoulos

—

The NISQ Complexity of Collision Finding (2022)

Yassine Hamoudi et al.

—

Post-Quantum κ-to-1 Trapdoor Claw-free Functions from Extrapolated Dihedral Cosets (2022)

Xingyu Yan (1) et al.

—

Quantum Cryptography in Algorithmica (2022)

William Kretschmer et al.

—

Towards Separating Computational and Statistical Differential Privacy (2023)

Badih Ghazi and Rahul Ilango and Pritish Kamath and Ravi Kumar and Pasin Manurangsi

—

On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions (2023)

Prabhanjan Ananth et al.

—

Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions (2023)

Fuyuki Kitagawa et al.

—

Hardness of Deceptive Certificate Selection (2023)

Stephan W\"aldchen

—

Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher (2023)

Akinori Kawachi and Yuki Naito

—

The Complexity of Verifying Boolean Programs as Differentially Private (2023)

Mark Bun et al.

—

On the accuracy and efficiency of group-wise clipping in differentially private optimization (2023)

Zhiqi Bu et al.

—

Pseudorandom Isometries (2023)

Prabhanjan Ananth et al.

—

An efficient quantum parallel repetition theorem and applications (2023)

John Bostanci et al.

—

Zero redundancy distributed learning with differential privacy (2023)

Zhiqi Bu et al.

—

Lightweight Public Key Encryption in Post-Quantum Computing Era (2023)

Peter Hillmann

—

On the complexity of sabotage games for network security (2023)

Dhananjay Raju et al.

—

A Note on Output Length of One-Way State Generators and EFIs (2023)

Minki Hhan and Tomoyuki Morimae and Takashi Yamakawa

—

Optimally Blending Honeypots into Production Networks: Hardness and Algorithms (2024)

Md Mahabub Uz Zaman et al.

—

Perfect Zero-Knowledge PCPs for #P (2024)

Tom Gur et al.

—

Awesome Computational Complexity

Key papers

Computational Complexity

Awesome Computational Complexity

Key papers