A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. - Andrej Bogdanov; Kenji Obata; Luca Trevisan 001 (FOCS, 2002)

Mechanical Translation of I/O Automaton Specifications into First-Order Logic. - Andrej Bogdanov; Stephen J. Garland; Nancy A. Lynch (FORTE, 2002)

Lower Bounds for Testing Bipartiteness in Dense Graphs - Andrej Bogdanov; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2002)

A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes. - Andrej Bogdanov; Hoeteck Wee (APPROX-RANDOM, 2004)

Power-aware base station positioning for sensor networks. - Andrej Bogdanov; Elitza N. Maneva; Samantha J. Riesenfeld (INFOCOM, 2004)

More on Noncommutative Polynomial Identity Testing. - Andrej Bogdanov; Hoeteck Wee (CCC, 2005)

Pseudorandom generators for low degree polynomials. - Andrej Bogdanov (STOC, 2005)

Average-Case Complexity. - Andrej Bogdanov; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2006)

On Worst-Case to Average-Case Reductions for NP Problems. - Andrej Bogdanov; Luca Trevisan 001 (SIAM J. Comput., 2006)

Hardness amplification for errorless heuristics. - Andrej Bogdanov; Muli Safra (Electron. Colloquium Comput. Complex., 2007)

The Complexity of Distinguishing Markov Random Fields. - Andrej Bogdanov; Elchanan Mossel; Salil P. Vadhan (APPROX-RANDOM, 2008)

Pseudorandomness for Width 2 Branching Programs. - Andrej Bogdanov; Zeev Dvir; Elad Verbin; Amir Yehudayoff (Electron. Colloquium Comput. Complex., 2009)

Hard Instances for Satisfiability and Quasi-one-way Functions. - Andrej Bogdanov; Kunal Talwar; Andrew Wan (ICS, 2010)

The Computational Complexity of Estimating Convergence Time - Nayantara Bhatnagar; Andrej Bogdanov; Elchanan Mossel (CoRR, 2010)

A better tester for bipartiteness? - Andrej Bogdanov; Fan Li (CoRR, 2010)

Pseudorandom Bits for Polynomials. - Andrej Bogdanov; Emanuele Viola (SIAM J. Comput., 2010)

The Computational Complexity of Estimating MCMC Convergence Time. - Nayantara Bhatnagar; Andrej Bogdanov; Elchanan Mossel (APPROX-RANDOM, 2011)

A Dichotomy for Local Small-Bias Generators. - Benny Applebaum; Andrej Bogdanov; Alon Rosen (Electron. Colloquium Comput. Complex., 2011)

Pseudorandomness for read-once formulas. - Andrej Bogdanov; Periklis A. Papakonstantinou; Andrew Wan (Electron. Colloquium Comput. Complex., 2011)

Input locality and hardness amplification. - Andrej Bogdanov; Alon Rosen (Electron. Colloquium Comput. Complex., 2011)

Homomorphic encryption from codes. - Andrej Bogdanov; Chin Ho Lee (IACR Cryptol. ePrint Arch., 2011)

On Extracting Common Random Bits From Correlated Sources. - Andrej Bogdanov; Elchanan Mossel (IEEE Trans. Inf. Theory, 2011)

Pseudorandomness for Linear Length Branching Programs and Stack Machines. - Andrej Bogdanov; Periklis A. Papakonstantinou; Andrew Wan (APPROX-RANDOM, 2012)

On the security of Goldreich's one-way function. - Andrej Bogdanov; Youming Qiao (Comput. Complex., 2012)

Sparse extractor families for all the entropy. - Andrej Bogdanov; Siyao Guo (Electron. Colloquium Comput. Complex., 2012)

Limits of provable security for homomorphic encryption. - Andrej Bogdanov; Chin Ho Lee (Electron. Colloquium Comput. Complex., 2012)

On the depth complexity of homomorphic encryption schemes. - Andrej Bogdanov; Chin Ho Lee (Electron. Colloquium Comput. Complex., 2012)

Hard Functions for Low-Degree Polynomials over Prime Fields. - Andrej Bogdanov; Akinori Kawachi; Hidetoki Tanaka (ACM Trans. Comput. Theory, 2013)

Candidate weak pseudorandom functions in AC0 ○ MOD2. - Adi Akavia; Andrej Bogdanov; Siyao Guo; Akshay Kamath; Alon Rosen (Electron. Colloquium Comput. Complex., 2014)

On Basing Size-Verifiable One-Way Functions on NP-Hardness. - Andrej Bogdanov; Christina Brzuska (Electron. Colloquium Comput. Complex., 2014)

Bounded Indistinguishability and the Complexity of Recovering Secrets. - Andrej Bogdanov; Yuval Ishai; Emanuele Viola; Christopher Williamson (Electron. Colloquium Comput. Complex., 2015)

On the Hardness of Learning with Rounding over Small Modulus. - Andrej Bogdanov; Siyao Guo; Daniel Masny; Silas Richelson; Alon Rosen (IACR Cryptol. ePrint Arch., 2015)

Homomorphic evaluation requires depth. - Andrej Bogdanov; Chin Ho Lee (IACR Cryptol. ePrint Arch., 2015)

Threshold Secret Sharing Requires a Linear Size Alphabet. - Andrej Bogdanov; Siyao Guo; Ilan Komargodski (Electron. Colloquium Comput. Complex., 2016)

Pseudorandom Functions: Three Decades Later. - Andrej Bogdanov; Alon Rosen (Tutorials on the Foundations of Cryptography, 2017)

Approximate Bounded Indistinguishability. - Andrej Bogdanov; Christopher Williamson (ICALP, 2017)

Complete Classification of Generalized Santha-Vazirani Sources. - Salman Beigi; Andrej Bogdanov; Omid Etesami; Siyao Guo (CoRR, 2017)

Complete Classi fication of Generalized Santha-Vazirani Sources. - Salman Beigi; Andrej Bogdanov; Omid Etesami; Siyao Guo (Electron. Colloquium Comput. Complex., 2017)

Small bias requires large formulas. - Andrej Bogdanov (Electron. Colloquium Comput. Complex., 2017)

Pseudorandom Functions: Three Decades Later. - Andrej Bogdanov; Alon Rosen (Electron. Colloquium Comput. Complex., 2017)

Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources. - Salman Beigi; Andrej Bogdanov; Omid Etesami; Siyao Guo (APPROX-RANDOM, 2018)

Approximate degree of AND via Fourier analysis. - Andrej Bogdanov (Electron. Colloquium Comput. Complex., 2018)

XOR Codes and Sparse Random Linear Equations with Noise. - Andrej Bogdanov; Manuel Sabin; Prashant Nalini Vasudevan (Electron. Colloquium Comput. Complex., 2018)

When are large codes possible for AVCs? - Xishi Nicholas Wang; Amitalok J. Budkuley; Andrej Bogdanov; Sidharth Jaggi (ISIT, 2019)

XOR Codes and Sparse Learning Parity with Noise. - Andrej Bogdanov; Manuel Sabin; Prashant Nalini Vasudevan (SODA, 2019)

Approximate degree, secret sharing, and concentration phenomena. - Andrej Bogdanov; Nikhil S. Mande; Justin Thaler; Christopher Williamson (Electron. Colloquium Comput. Complex., 2019)

Learning and Testing Variable Partitions. - Andrej Bogdanov; Baoxiang Wang 001 (ITCS, 2020)

Direct Sum and Partitionability Testing over General Groups. - Andrej Bogdanov; Gautam Prakriya (Electron. Colloquium Comput. Complex., 2020)

A Gentle Introduction to Zero-Knowledge. - Andrej Bogdanov (ICT Innovations, 2021)

On quantum versus classical query complexity. - Scott Aaronson; Andris Ambainis; Andrej Bogdanov; Krishnamoorthy Dinesh 001; Tsun Ming Cheung (Electron. Colloquium Comput. Complex., 2021)

Bounded Indistinguishability for Simple Sources. - Andrej Bogdanov; Krishnamoorthy Dinesh 001; Yuval Filmus; Yuval Ishai; Avi Kaplan; Akshayaram Srinivasan (Electron. Colloquium Comput. Complex., 2021)

Acyclicity Programming for Sigma-Protocols. - Masayuki Abe; Miguel Ambrona; Andrej Bogdanov; Miyako Ohkubo; Alon Rosen (IACR Cryptol. ePrint Arch., 2021)

Non-Interactive Composition of Sigma-Protocols via Share-then-Hash. - Masayuki Abe; Miguel Ambrona; Andrej Bogdanov; Miyako Ohkubo; Alon Rosen (IACR Cryptol. ePrint Arch., 2021)

Unconditionally Secure Computation Against Low-Complexity Leakage. - Andrej Bogdanov; Yuval Ishai; Akshayaram Srinivasan (J. Cryptol., 2021)

Hitting Sets for Regular Branching Programs. - Andrej Bogdanov; William M. Hoza; Gautam Prakriya; Edward Pyne (CCC, 2022)

Public-Key Encryption from Homogeneous CLWE. - Andrej Bogdanov; Miguel Cueto Noval; Charlotte Hoffmann; Alon Rosen (TCC (2), 2022)

Public-Key Encryption from Continuous LWE. - Andrej Bogdanov; Miguel Cueto Noval; Charlotte Hoffmann; Alon Rosen (Electron. Colloquium Comput. Complex., 2022)

Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage. - Andrej Bogdanov; Yuval Ishai; Akshayaram Srinivasan (J. Cryptol., 2022)

Csirmaz's Duality Conjecture and Threshold Secret Sharing. - Andrej Bogdanov (ITC, 2023)

Bounded Simultaneous Messages. - Andrej Bogdanov; Krishnamoorthy Dinesh 001; Yuval Filmus; Yuval Ishai; Avi Kaplan; Sruthi Sekar (FSTTCS, 2023)

Nondeterministic Interactive Refutations for Nearest Boolean Vector. - Andrej Bogdanov; Alon Rosen (ICALP, 2023)

Classical simulation of one-query quantum distinguishers. - Andrej Bogdanov; TsunMing Cheung; Krishnamoorthy Dinesh 001; John C. S. Lui (Electron. Colloquium Comput. Complex., 2023)

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. - Andrej Bogdanov; Pravesh Kothari; Alon Rosen (Electron. Colloquium Comput. Complex., 2023)

CDS Composition of Multi-round Protocols. - Masayuki Abe; Andrej Bogdanov; Miyako Ohkubo; Alon Rosen; Zehua Shang; Mehdi Tibouchi (CRYPTO (9), 2024)

Towards a Scalable Reference-Free Evaluation of Generative Models. - Azim Ospanov; Jingwei Zhang; Mohammad Jalali; Xuenan Cao; Andrej Bogdanov; Farzan Farnia (NeurIPS, 2024)

Low-degree Security of the Planted Random Subgraph Problem. - Andrej Bogdanov; Chris Jones; Alon Rosen; Ilias Zadik (IACR Cryptol. ePrint Arch., 2024)

Estimating Euclidean Distance to Linearity. - Andrej Bogdanov; Lorenzo Taschin (ITCS, 2025)

Sample Efficient Search to Decision for kLIN. - Andrej Bogdanov; Alon Rosen; Kel Zin Tan (IACR Cryptol. ePrint Arch., 2025)

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss. - Andrej Bogdanov; Alon Rosen; Neekon Vafa; Vinod Vaikuntanathan (IACR Cryptol. ePrint Arch., 2025)