Andrej Bogdanov

128 papers A* 13A 12B 4C 1Journal 74Unranked 23
YearRankTypeTitle / Venue / Authors
2026 A conf
Decoding Balanced Linear Codes with Preprocessing.
ITCS
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
2025 J jnl
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss.
CoRR
Andrej Bogdanov, Alon Rosen, Neekon Vafa, Vinod Vaikuntanathan
2025 J jnl
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Alon Rosen, Neekon Vafa, Vinod Vaikuntanathan
2025 J jnl
Are Neural Networks Collision Resistant?
CoRR
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina
2025 J jnl
Are Neural Networks Collision Resistant?
IACR Cryptol. ePrint Arch.
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina
2025 J jnl
Decoding Balanced Linear Codes With Preprocessing.
CoRR
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
2025 J jnl
Decoding Balanced Linear Codes With Preprocessing.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
2025 J jnl
Decoding Balanced Linear Codes With Preprocessing.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
2025 A conf
Estimating Euclidean Distance to Linearity.
ITCS
Andrej Bogdanov, Lorenzo Taschin
2025 — conf
Sample Efficient Search to Decision for kLIN.
CRYPTO (1)
Andrej Bogdanov, Alon Rosen, Kel Zin Tan
2025 J jnl
Sample Efficient Search to Decision for kLIN.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Alon Rosen, Kel Zin Tan
2024 — conf
CDS Composition of Multi-round Protocols.
CRYPTO (9)
Masayuki Abe, Andrej Bogdanov, Miyako Ohkubo, Alon Rosen, Zehua Shang, Mehdi Tibouchi
2024 — conf
Low-Degree Security of the Planted Random Subgraph Problem.
TCC (2)
Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik
2024 J jnl
Low-degree Security of the Planted Random Subgraph Problem.
CoRR
Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik
2024 J jnl
Low-degree Security of the Planted Random Subgraph Problem.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik
2024 A* conf
Towards a Scalable Reference-Free Evaluation of Generative Models.
NeurIPS
Azim Ospanov, Jingwei Zhang, Mohammad Jalali, Xuenan Cao, Andrej Bogdanov, Farzan Farnia
2024 J jnl
Towards a Scalable Reference-Free Evaluation of Generative Models.
CoRR
Azim Ospanov, Jingwei Zhang, Mohammad Jalali, Xuenan Cao, Andrej Bogdanov, Farzan Farnia
2023 — conf
Bounded Simultaneous Messages.
FSTTCS
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Sruthi Sekar
2023 J jnl
Bounded Simultaneous Messages.
CoRR
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Sruthi Sekar
2023 A conf
Classical Simulation of One-Query Quantum Distinguishers.
APPROX/RANDOM
Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, John C. S. Lui
2023 J jnl
Classical simulation of one-query quantum distinguishers.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, TsunMing Cheung, Krishnamoorthy Dinesh, John C. S. Lui
2023 A conf
Csirmaz's Duality Conjecture and Threshold Secret Sharing.
ITC
Andrej Bogdanov
2023 A* conf
Nondeterministic Interactive Refutations for Nearest Boolean Vector.
ICALP
Andrej Bogdanov, Alon Rosen
2023 — conf
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.
TCC (1)
Andrej Bogdanov, Pravesh K. Kothari, Alon Rosen
2023 J jnl
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Pravesh Kothari, Alon Rosen
2023 J jnl
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Pravesh Kothari, Alon Rosen
2022 A conf
Bounded Indistinguishability for Simple Sources.
ITCS
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan
2022 J jnl
Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage.
J. Cryptol.
Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan
2022 J jnl
Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage.
J. Cryptol.
Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan
2022 A conf
Hitting Sets for Regular Branching Programs.
CCC
Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne
2022 J jnl
Public-Key Encryption from Continuous LWE.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen
2022 J jnl
Public-Key Encryption from Continuous LWE.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen
2022 — conf
Public-Key Encryption from Homogeneous CLWE.
TCC (2)
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen
2021 — conf
A Gentle Introduction to Zero-Knowledge.
ICT Innovations
Andrej Bogdanov
2021 — conf
Acyclicity Programming for Sigma-Protocols.
TCC (1)
Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, Alon Rosen
2021 J jnl
Acyclicity Programming for Sigma-Protocols.
IACR Cryptol. ePrint Arch.
Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, Alon Rosen
2021 J jnl
Bounded Indistinguishability for Simple Sources.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan
2021 A* conf
Direct Sum and Partitionability Testing over General Groups.
ICALP
Andrej Bogdanov, Gautam Prakriya
2021 J jnl
Non-Interactive Composition of Sigma-Protocols via Share-then-Hash.
IACR Cryptol. ePrint Arch.
Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, Alon Rosen
2021 J jnl
On quantum versus classical query complexity.
Electron. Colloquium Comput. Complex.
Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung
2021 J jnl
Unconditionally Secure Computation Against Low-Complexity Leakage.
J. Cryptol.
Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan
2020 J jnl
Direct Sum and Partitionability Testing over General Groups.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Gautam Prakriya
2020 A conf
Learning and Testing Variable Partitions.
ITCS
Andrej Bogdanov, Baoxiang Wang
2020 J jnl
Learning and Testing Variable Partitions.
CoRR
Andrej Bogdanov, Baoxiang Wang
2020 — conf
Non-interactive Composition of Sigma-Protocols via Share-then-Hash.
ASIACRYPT (3)
Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, Alon Rosen
2020 J jnl
Threshold Secret Sharing Requires a Linear-Size Alphabet.
Theory Comput.
Andrej Bogdanov, Siyao Guo, Ilan Komargodski
2019 — conf
Approximate Degree, Secret Sharing, and Concentration Phenomena.
APPROX-RANDOM
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
2019 J jnl
Approximate degree, secret sharing, and concentration phenomena.
CoRR
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
2019 J jnl
Approximate degree, secret sharing, and concentration phenomena.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson
2019 — conf
Unconditionally Secure Computation Against Low-Complexity Leakage.
CRYPTO (2)
Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan
2019 J jnl
Unconditionally Secure Computation Against Low-Complexity Leakage.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan
2019 B conf
When are large codes possible for AVCs?
ISIT
Xishi Nicholas Wang, Amitalok J. Budkuley, Andrej Bogdanov, Sidharth Jaggi
2019 A* conf
XOR Codes and Sparse Learning Parity with Noise.
SODA
Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan
2018 J jnl
Approximate degree of AND via Fourier analysis.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov
2018 — conf
Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources.
APPROX-RANDOM
Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo
2018 A* conf
Small Bias Requires Large Formulas.
ICALP
Andrej Bogdanov
2018 J jnl
XOR Codes and Sparse Random Linear Equations with Noise.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan
2017 A* conf
Approximate Bounded Indistinguishability.
ICALP
Andrej Bogdanov, Christopher Williamson
2017 J jnl
Complete Classi fication of Generalized Santha-Vazirani Sources.
Electron. Colloquium Comput. Complex.
Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo
2017 J jnl
Complete Classification of Generalized Santha-Vazirani Sources.
CoRR
Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo
2017 — ch.
Pseudorandom Functions: Three Decades Later.
Tutorials on the Foundations of Cryptography
Andrej Bogdanov, Alon Rosen
2017 J jnl
Pseudorandom Functions: Three Decades Later.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Alon Rosen
2017 J jnl
Pseudorandom Functions: Three Decades Later.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Alon Rosen
2017 J jnl
Small bias requires large formulas.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov
2016 J jnl
A Dichotomy for Local Small-Bias Generators.
J. Cryptol.
Benny Applebaum, Andrej Bogdanov, Alon Rosen
2016 — conf
Bounded Indistinguishability and the Complexity of Recovering Secrets.
CRYPTO (3)
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
2016 J jnl
Bounded Indistinguishability and the Complexity of Recovering Secrets.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
2016 — conf
Homomorphic Evaluation Requires Depth.
TCC (A1)
Andrej Bogdanov, Chin Ho Lee
2016 — conf
On the Hardness of Learning with Rounding over Small Modulus.
TCC (A1)
Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, Alon Rosen
2016 — conf
Threshold Secret Sharing Requires a Linear Size Alphabet.
TCC (B2)
Andrej Bogdanov, Siyao Guo, Ilan Komargodski
2016 J jnl
Threshold Secret Sharing Requires a Linear Size Alphabet.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Siyao Guo, Ilan Komargodski
2015 J jnl
Bounded Indistinguishability and the Complexity of Recovering Secrets.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson
2015 J jnl
Homomorphic evaluation requires depth.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Chin Ho Lee
2015 — conf
On Basing Size-Verifiable One-Way Functions on NP-Hardness.
TCC (1)
Andrej Bogdanov, Christina Brzuska
2015 J jnl
On the Hardness of Learning with Rounding over Small Modulus.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, Alon Rosen
2014 A conf
Candidate weak pseudorandom functions in AC
ITCS
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen
2014 J jnl
Candidate weak pseudorandom functions in AC
Electron. Colloquium Comput. Complex.
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen
2014 J jnl
On Basing Size-Verifiable One-Way Functions on NP-Hardness.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Christina Brzuska
2013 J jnl
Hard Functions for Low-Degree Polynomials over Prime Fields.
ACM Trans. Comput. Theory
Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka
2013 J jnl
Input Locality and Hardness Amplification.
J. Cryptol.
Andrej Bogdanov, Alon Rosen
2013 — conf
Limits of Provable Security for Homomorphic Encryption.
CRYPTO (1)
Andrej Bogdanov, Chin Ho Lee
2013 J jnl
Limits of provable security for homomorphic encryption.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Chin Ho Lee
2013 J jnl
Pseudorandomness for Width-2 Branching Programs.
Theory Comput.
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff
2013 A conf
Sparse extractor families for all the entropy.
ITCS
Andrej Bogdanov, Siyao Guo
2012 B conf
A Dichotomy for Local Small-Bias Generators.
TCC
Benny Applebaum, Andrej Bogdanov, Alon Rosen
2012 J jnl
Limits of provable security for homomorphic encryption.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Chin Ho Lee
2012 J jnl
On the depth complexity of homomorphic encryption schemes.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Chin Ho Lee
2012 J jnl
On the security of Goldreich's one-way function.
Comput. Complex.
Andrej Bogdanov, Youming Qiao
2012 — conf
Pseudorandomness for Linear Length Branching Programs and Stack Machines.
APPROX-RANDOM
Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan
2012 J jnl
Sparse extractor families for all the entropy
CoRR
Andrej Bogdanov, Siyao Guo
2012 J jnl
Sparse extractor families for all the entropy.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Siyao Guo
2011 J jnl
A Dichotomy for Local Small-Bias Generators.
Electron. Colloquium Comput. Complex.
Benny Applebaum, Andrej Bogdanov, Alon Rosen
2011 J jnl
A Dichotomy for Local Small-Bias Generators.
IACR Cryptol. ePrint Arch.
Benny Applebaum, Andrej Bogdanov, Alon Rosen
2011 B conf
Hard Functions for Low-Degree Polynomials over Prime Fields.
MFCS
Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka
2011 J jnl
Homomorphic encryption from codes
CoRR
Andrej Bogdanov, Chin Ho Lee
2011 J jnl
Homomorphic encryption from codes.
IACR Cryptol. ePrint Arch.
Andrej Bogdanov, Chin Ho Lee
2011 B conf
Input Locality and Hardness Amplification.
TCC
Andrej Bogdanov, Alon Rosen
2011 J jnl
Input locality and hardness amplification.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Alon Rosen
2011 J jnl
On Extracting Common Random Bits From Correlated Sources.
IEEE Trans. Inf. Theory
Andrej Bogdanov, Elchanan Mossel
2011 A* conf
Pseudorandomness for Read-Once Formulas.
FOCS
Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan
2011 J jnl
Pseudorandomness for read-once formulas.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan
2011 — conf
The Computational Complexity of Estimating MCMC Convergence Time.
APPROX-RANDOM
Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel
2010 J jnl
A better tester for bipartiteness?
CoRR
Andrej Bogdanov, Fan Li
2010 A conf
Hard Instances for Satisfiability and Quasi-one-way Functions.
ICS
Andrej Bogdanov, Kunal Talwar, Andrew Wan
2010 J jnl
On extracting common random bits from correlated sources
CoRR
Andrej Bogdanov, Elchanan Mossel
2010 J jnl
Pseudorandom Bits for Polynomials.
SIAM J. Comput.
Andrej Bogdanov, Emanuele Viola
2010 J jnl
The Computational Complexity of Estimating Convergence Time
CoRR
Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel
2009 — conf
On the Security of Goldreich's One-Way Function.
APPROX-RANDOM
Andrej Bogdanov, Youming Qiao
2009 J jnl
Pseudorandomness for Width 2 Branching Programs.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff
2008 — conf
The Complexity of Distinguishing Markov Random Fields.
APPROX-RANDOM
Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan
2007 A* conf
Hardness Amplification for Errorless Heuristics.
FOCS
Andrej Bogdanov, Muli Safra
2007 J jnl
Hardness amplification for errorless heuristics.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Muli Safra
2007 A* conf
Pseudorandom Bits for Polynomials.
FOCS
Andrej Bogdanov, Emanuele Viola
2007 J jnl
Pseudorandom bits for polynomials.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Emanuele Viola
2006 J jnl
Average-Case Complexity
CoRR
Andrej Bogdanov, Luca Trevisan
2006 J jnl
Average-Case Complexity.
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Luca Trevisan
2006 J jnl
Average-Case Complexity.
Found. Trends Theor. Comput. Sci.
Andrej Bogdanov, Luca Trevisan
2006 J jnl
On Worst-Case to Average-Case Reductions for NP Problems.
SIAM J. Comput.
Andrej Bogdanov, Luca Trevisan
2005 A conf
More on Noncommutative Polynomial Identity Testing.
CCC
Andrej Bogdanov, Hoeteck Wee
2005 J jnl
On Worst-Case to Average-Case Reductions for NP Problems
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Luca Trevisan
2005 A* conf
Pseudorandom generators for low degree polynomials.
STOC
Andrej Bogdanov
2004 — conf
A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes.
APPROX-RANDOM
Andrej Bogdanov, Hoeteck Wee
2004 A conf
Lower Bounds for Testing Bipartiteness in Dense Graphs.
CCC
Andrej Bogdanov, Luca Trevisan
2004 A* conf
Power-aware base station positioning for sensor networks.
INFOCOM
Andrej Bogdanov, Elitza N. Maneva, Samantha J. Riesenfeld
2003 A* conf
On Worst-Case to Average-Case Reductions for NP Problems.
FOCS
Andrej Bogdanov, Luca Trevisan
2002 A* conf
A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.
FOCS
Andrej Bogdanov, Kenji Obata, Luca Trevisan
2002 J jnl
Lower Bounds for Testing Bipartiteness in Dense Graphs
Electron. Colloquium Comput. Complex.
Andrej Bogdanov, Luca Trevisan
2002 C conf
Mechanical Translation of I/O Automaton Specifications into First-Order Logic.
FORTE
Andrej Bogdanov, Stephen J. Garland, Nancy A. Lynch