Andrej Bogdanov

Orcid: 0000-0002-0338-6151

According to our database1, Andrej Bogdanov authored at least 66 papers between 2002 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Low-degree Security of the Planted Random Subgraph Problem.
IACR Cryptol. ePrint Arch., 2024

Towards a Scalable Reference-Free Evaluation of Generative Models.
CoRR, 2024

CDS Composition of Multi-round Protocols.
Proceedings of the Advances in Cryptology - CRYPTO 2024, 2024

2023
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method.
Electron. Colloquium Comput. Complex., 2023

Classical simulation of one-query quantum distinguishers.
Electron. Colloquium Comput. Complex., 2023

Nondeterministic Interactive Refutations for Nearest Boolean Vector.
Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Bounded Simultaneous Messages.
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.
Proceedings of the 4th Conference on Information-Theoretic Cryptography, 2023

2022
Correction to: Unconditionally Secure Computation Against Low-Complexity Leakage.
J. Cryptol., 2022

Public-Key Encryption from Continuous LWE.
Electron. Colloquium Comput. Complex., 2022

Public-Key Encryption from Homogeneous CLWE.
Proceedings of the Theory of Cryptography - 20th International Conference, 2022

Hitting Sets for Regular Branching Programs.
Proceedings of the 37th Computational Complexity Conference, 2022

2021
Unconditionally Secure Computation Against Low-Complexity Leakage.
J. Cryptol., 2021

Non-Interactive Composition of Sigma-Protocols via Share-then-Hash.
IACR Cryptol. ePrint Arch., 2021

Acyclicity Programming for Sigma-Protocols.
IACR Cryptol. ePrint Arch., 2021

Bounded Indistinguishability for Simple Sources.
Electron. Colloquium Comput. Complex., 2021

On quantum versus classical query complexity.
Electron. Colloquium Comput. Complex., 2021

A Gentle Introduction to Zero-Knowledge.
Proceedings of the ICT Innovations 2021. Digital Transformation, 2021

2020
Direct Sum and Partitionability Testing over General Groups.
Electron. Colloquium Comput. Complex., 2020

Learning and Testing Variable Partitions.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019
Approximate degree, secret sharing, and concentration phenomena.
Electron. Colloquium Comput. Complex., 2019

XOR Codes and Sparse Learning Parity with Noise.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

When are large codes possible for AVCs?
Proceedings of the IEEE International Symposium on Information Theory, 2019

2018
XOR Codes and Sparse Random Linear Equations with Noise.
Electron. Colloquium Comput. Complex., 2018

Approximate degree of AND via Fourier analysis.
Electron. Colloquium Comput. Complex., 2018

Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources.
Proceedings of the Approximation, 2018

2017
Pseudorandom Functions: Three Decades Later.
Electron. Colloquium Comput. Complex., 2017

Small bias requires large formulas.
Electron. Colloquium Comput. Complex., 2017

Complete Classi fication of Generalized Santha-Vazirani Sources.
Electron. Colloquium Comput. Complex., 2017

Complete Classification of Generalized Santha-Vazirani Sources.
CoRR, 2017

Approximate Bounded Indistinguishability.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Pseudorandom Functions: Three Decades Later.
Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016
Threshold Secret Sharing Requires a Linear Size Alphabet.
Electron. Colloquium Comput. Complex., 2016

2015
Homomorphic evaluation requires depth.
IACR Cryptol. ePrint Arch., 2015

On the Hardness of Learning with Rounding over Small Modulus.
IACR Cryptol. ePrint Arch., 2015

Bounded Indistinguishability and the Complexity of Recovering Secrets.
Electron. Colloquium Comput. Complex., 2015

2014
On Basing Size-Verifiable One-Way Functions on NP-Hardness.
Electron. Colloquium Comput. Complex., 2014

Candidate weak pseudorandom functions in AC<sup>0</sup> ○ MOD<sub>2</sub>.
Electron. Colloquium Comput. Complex., 2014

2013
Hard Functions for Low-Degree Polynomials over Prime Fields.
ACM Trans. Comput. Theory, 2013

2012
On the depth complexity of homomorphic encryption schemes.
Electron. Colloquium Comput. Complex., 2012

Limits of provable security for homomorphic encryption.
Electron. Colloquium Comput. Complex., 2012

Sparse extractor families for all the entropy.
Electron. Colloquium Comput. Complex., 2012

On the security of Goldreich's one-way function.
Comput. Complex., 2012

Pseudorandomness for Linear Length Branching Programs and Stack Machines.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
On Extracting Common Random Bits From Correlated Sources.
IEEE Trans. Inf. Theory, 2011

Homomorphic encryption from codes.
IACR Cryptol. ePrint Arch., 2011

Input locality and hardness amplification.
Electron. Colloquium Comput. Complex., 2011

Pseudorandomness for read-once formulas.
Electron. Colloquium Comput. Complex., 2011

A Dichotomy for Local Small-Bias Generators.
Electron. Colloquium Comput. Complex., 2011

The Computational Complexity of Estimating MCMC Convergence Time.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Pseudorandom Bits for Polynomials.
SIAM J. Comput., 2010

A better tester for bipartiteness?
CoRR, 2010

The Computational Complexity of Estimating Convergence Time
CoRR, 2010

Hard Instances for Satisfiability and Quasi-one-way Functions.
Proceedings of the Innovations in Computer Science, 2010

2009
Pseudorandomness for Width 2 Branching Programs.
Electron. Colloquium Comput. Complex., 2009

2008
The Complexity of Distinguishing Markov Random Fields.
Proceedings of the Approximation, 2008

2007
Hardness amplification for errorless heuristics.
Electron. Colloquium Comput. Complex., 2007

2006
On Worst-Case to Average-Case Reductions for NP Problems.
SIAM J. Comput., 2006

Average-Case Complexity.
Electron. Colloquium Comput. Complex., 2006

2005
Pseudorandom generators for low degree polynomials.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

More on Noncommutative Polynomial Identity Testing.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004
Power-aware base station positioning for sensor networks.
Proceedings of the Proceedings IEEE INFOCOM 2004, 2004

A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes.
Proceedings of the Approximation, 2004

2002
Lower Bounds for Testing Bipartiteness in Dense Graphs
Electron. Colloquium Comput. Complex., 2002

Mechanical Translation of I/O Automaton Specifications into First-Order Logic.
Proceedings of the Formal Techniques for Networked and Distributed Systems, 2002

A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002


  Loading...