Andrej Bogdanov

According to our database, Andrej Bogdanov authored at least 63 papers between 2002 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.

Andrej Bogdanov, Pravesh Kothari, Alon Rosen

Electron. Colloquium Comput. Complex., 2023

Classical simulation of one-query quantum distinguishers.

Andrej Bogdanov, TsunMing Cheung, Krishnamoorthy Dinesh, John C. S. Lui

Electron. Colloquium Comput. Complex., 2023

Nondeterministic Interactive Refutations for Nearest Boolean Vector.

Andrej Bogdanov, Alon Rosen

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Bounded Simultaneous Messages.

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Sruthi Sekar

Proceedings of the 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2023

Csirmaz's Duality Conjecture and Threshold Secret Sharing.

Andrej Bogdanov

Proceedings of the 4th Conference on Information-Theoretic Cryptography, 2023

2022

Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage.

Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan

J. Cryptol., 2022

Public-Key Encryption from Continuous LWE.

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

Electron. Colloquium Comput. Complex., 2022

Public-Key Encryption from Homogeneous CLWE.

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

Proceedings of the Theory of Cryptography - 20th International Conference, 2022

Hitting Sets for Regular Branching Programs.

Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Unconditionally Secure Computation Against Low-Complexity Leakage.

Andrej Bogdanov, Yuval Ishai, Akshayaram Srinivasan

J. Cryptol., 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

Acyclicity Programming for Sigma-Protocols.

Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Ohkubo, Alon Rosen

IACR Cryptol. ePrint Arch., 2021

Bounded Indistinguishability for Simple Sources.

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

Electron. Colloquium Comput. Complex., 2021

On quantum versus classical query complexity.

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung

Electron. Colloquium Comput. Complex., 2021

A Gentle Introduction to Zero-Knowledge.

Andrej Bogdanov

Proceedings of the ICT Innovations 2021. Digital Transformation, 2021

2020

Threshold Secret Sharing Requires a Linear-Size Alphabet.

Andrej Bogdanov, Siyao Guo, Ilan Komargodski

Theory Comput., 2020

Direct Sum and Partitionability Testing over General Groups.

Andrej Bogdanov, Gautam Prakriya

Electron. Colloquium Comput. Complex., 2020

Learning and Testing Variable Partitions.

Andrej Bogdanov, Baoxiang Wang

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Approximate degree, secret sharing, and concentration phenomena.

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson

Electron. Colloquium Comput. Complex., 2019

XOR Codes and Sparse Learning Parity with Noise.

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

When are large codes possible for AVCs?

Xishi Nicholas Wang, Amitalok J. Budkuley, Andrej Bogdanov, Sidharth Jaggi

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

XOR Codes and Sparse Random Linear Equations with Noise.

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

Electron. Colloquium Comput. Complex., 2018

Approximate degree of AND via Fourier analysis.

Andrej Bogdanov

Electron. Colloquium Comput. Complex., 2018

Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources.

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Proceedings of the Approximation, 2018

2017

Pseudorandom Functions: Three Decades Later.

Andrej Bogdanov, Alon Rosen

Electron. Colloquium Comput. Complex., 2017

Small bias requires large formulas.

Andrej Bogdanov

Electron. Colloquium Comput. Complex., 2017

Complete Classi fication of Generalized Santha-Vazirani Sources.

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Electron. Colloquium Comput. Complex., 2017

Complete Classification of Generalized Santha-Vazirani Sources.

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

CoRR, 2017

Approximate Bounded Indistinguishability.

Andrej Bogdanov, Christopher Williamson

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Pseudorandom Functions: Three Decades Later.

Andrej Bogdanov, Alon Rosen

Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016

A Dichotomy for Local Small-Bias Generators.

Benny Applebaum, Andrej Bogdanov, Alon Rosen

J. Cryptol., 2016

2015

Homomorphic evaluation requires depth.

Andrej Bogdanov, Chin Ho Lee

IACR Cryptol. ePrint Arch., 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

Bounded Indistinguishability and the Complexity of Recovering Secrets.

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

Electron. Colloquium Comput. Complex., 2015

2014

On Basing Size-Verifiable One-Way Functions on NP-Hardness.

Andrej Bogdanov, Christina Brzuska

Electron. Colloquium Comput. Complex., 2014

Candidate weak pseudorandom functions in AC⁰ ○ MOD₂.

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Electron. Colloquium Comput. Complex., 2014

2013

Hard Functions for Low-Degree Polynomials over Prime Fields.

Andrej Bogdanov, Akinori Kawachi, Hidetoki Tanaka

ACM Trans. Comput. Theory, 2013

Pseudorandomness for Width-2 Branching Programs.

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Theory Comput., 2013

Input Locality and Hardness Amplification.

Andrej Bogdanov, Alon Rosen

J. Cryptol., 2013

2012

On the depth complexity of homomorphic encryption schemes.

Andrej Bogdanov, Chin Ho Lee

Electron. Colloquium Comput. Complex., 2012

Limits of provable security for homomorphic encryption.

Andrej Bogdanov, Chin Ho Lee

Electron. Colloquium Comput. Complex., 2012

Sparse extractor families for all the entropy.

Andrej Bogdanov, Siyao Guo

Electron. Colloquium Comput. Complex., 2012

On the security of Goldreich's one-way function.

Andrej Bogdanov, Youming Qiao

Comput. Complex., 2012

Pseudorandomness for Linear Length Branching Programs and Stack Machines.

Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On Extracting Common Random Bits From Correlated Sources.

Andrej Bogdanov, Elchanan Mossel

IEEE Trans. Inf. Theory, 2011

Homomorphic encryption from codes.

Andrej Bogdanov, Chin Ho Lee

IACR Cryptol. ePrint Arch., 2011

Pseudorandomness for read-once formulas.

Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan

Electron. Colloquium Comput. Complex., 2011

The Computational Complexity of Estimating MCMC Convergence Time.

Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A better tester for bipartiteness?

Andrej Bogdanov, Fan Li

CoRR, 2010

The Computational Complexity of Estimating Convergence Time

Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel

CoRR, 2010

Hard Instances for Satisfiability and Quasi-one-way Functions.

Andrej Bogdanov, Kunal Talwar, Andrew Wan

Proceedings of the Innovations in Computer Science, 2010

2008

The Complexity of Distinguishing Markov Random Fields.

Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan

Proceedings of the Approximation, 2008

2007

Pseudorandom bits for polynomials.

Andrej Bogdanov, Emanuele Viola

Electron. Colloquium Comput. Complex., 2007

Hardness amplification for errorless heuristics.

Andrej Bogdanov, Muli Safra

Electron. Colloquium Comput. Complex., 2007

2006

Average-Case Complexity.

Andrej Bogdanov, Luca Trevisan

Electron. Colloquium Comput. Complex., 2006

2005

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

Andrej Bogdanov, Luca Trevisan

Electron. Colloquium Comput. Complex., 2005

Pseudorandom generators for low degree polynomials.

Andrej Bogdanov

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

More on Noncommutative Polynomial Identity Testing.

Andrej Bogdanov, Hoeteck Wee

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Power-aware base station positioning for sensor networks.

Andrej Bogdanov, Elitza N. Maneva, Samantha J. Riesenfeld

Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes.

Andrej Bogdanov, Hoeteck Wee

Proceedings of the Approximation, 2004

2002

Lower Bounds for Testing Bipartiteness in Dense Graphs

Andrej Bogdanov, Luca Trevisan

Electron. Colloquium Comput. Complex., 2002

Mechanical Translation of I/O Automaton Specifications into First-Order Logic.

Andrej Bogdanov, Stephen J. Garland, Nancy A. Lynch

Proceedings of the Formal Techniques for Networked and Distributed Systems, 2002

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.

Andrej Bogdanov, Kenji Obata, Luca Trevisan

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002