All reports by Author Andrej Bogdanov:

__
TR22-011
| 25th January 2022
__

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen#### Public-Key Encryption from Continuous LWE

__
TR21-115
| 6th August 2021
__

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming#### On quantum versus classical query complexity

Revisions: 2

__
TR21-093
| 1st July 2021
__

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan#### Bounded Indistinguishability for Simple Sources

Revisions: 1

__
TR20-164
| 9th November 2020
__

Andrej Bogdanov, Gautam Prakriya#### Direct Sum and Partitionability Testing over General Groups

Revisions: 1

__
TR19-082
| 2nd June 2019
__

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson#### Approximate degree, secret sharing, and concentration phenomena

__
TR18-197
| 22nd November 2018
__

Andrej Bogdanov#### Approximate degree of AND via Fourier analysis

Revisions: 1

__
TR18-085
| 26th April 2018
__

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan#### XOR Codes and Sparse Random Linear Equations with Noise

__
TR17-136
| 10th September 2017
__

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo#### Complete Classification of Generalized Santha-Vazirani Sources

__
TR17-113
| 1st July 2017
__

Andrej Bogdanov, Alon Rosen#### Pseudorandom Functions: Three Decades Later

__
TR17-091
| 17th May 2017
__

Andrej Bogdanov#### Small bias requires large formulas

Revisions: 1

__
TR16-131
| 21st August 2016
__

Andrej Bogdanov, Siyao Guo, Ilan Komargodski#### Threshold Secret Sharing Requires a Linear Size Alphabet

__
TR15-182
| 13th November 2015
__

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson#### Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

__
TR14-108
| 10th August 2014
__

Andrej Bogdanov, Christina Brzuska#### On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

__
TR14-033
| 10th March 2014
__

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

__
TR12-157
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### On the depth complexity of homomorphic encryption schemes

Revisions: 2

__
TR12-156
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### Limits of provable security for homomorphic encryption

Revisions: 1

__
TR12-097
| 26th July 2012
__

Andrej Bogdanov, Siyao Guo#### Sparse extractor families for all the entropy

__
TR11-126
| 17th September 2011
__

Benny Applebaum, Andrej Bogdanov, Alon Rosen#### A Dichotomy for Local Small-Bias Generators

__
TR11-117
| 3rd September 2011
__

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan#### Pseudorandomness for read-once formulas

__
TR11-012
| 2nd February 2011
__

Andrej Bogdanov, Alon Rosen#### Input locality and hardness amplification

__
TR09-070
| 1st September 2009
__

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff#### Pseudorandomness for Width 2 Branching Programs

__
TR07-102
| 4th October 2007
__

Andrej Bogdanov, Muli Safra#### Hardness amplification for errorless heuristics

__
TR07-081
| 10th August 2007
__

Andrej Bogdanov, Emanuele Viola#### Pseudorandom bits for polynomials

__
TR06-073
| 8th June 2006
__

Andrej Bogdanov, Luca Trevisan#### Average-Case Complexity

Revisions: 1

__
TR05-015
| 27th January 2005
__

Andrej Bogdanov, Luca Trevisan#### On Worst-Case to Average-Case Reductions for NP Problems

__
TR02-064
| 14th November 2002
__

Andrej Bogdanov, Luca Trevisan#### Lower Bounds for Testing Bipartiteness in Dense Graphs

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

The continuous learning with errors (CLWE) problem was recently introduced by Bruna

et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian

mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus

asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and

LWE ...
more >>>

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

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>

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

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et ... more >>>

Andrej Bogdanov, Gautam Prakriya

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

Andrej Bogdanov

We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we confirm that the approximate degree of any read-once depth-2 De Morgan formula ... more >>>

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

A $k$-LIN instance is a system of $m$ equations over $n$ variables of the form $s_{i[1]} + \dots + s_{i[k]} =$ 0 or 1 modulo 2 (each involving $k$ variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are ... more >>>

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

Andrej Bogdanov, Alon Rosen

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds.

In ... more >>>

Andrej Bogdanov

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

Andrej Bogdanov, Siyao Guo, Ilan Komargodski

We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$ threshold secret sharing scheme for one-bit secrets requires share size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a prime power. In 1990 Kilian and Nisan proved ... more >>>

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

Andrej Bogdanov, Christina Brzuska

We prove that if the hardness of inverting a size-verifiable one-way function can

be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This

claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but

was later retracted (STOC 2010).

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

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

Andrej Bogdanov, Siyao Guo

We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of ... more >>>

Benny Applebaum, Andrej Bogdanov, Alon Rosen

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

Andrej Bogdanov, Alon Rosen

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom

generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary

constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a

time. This ...
more >>>

Andrej Bogdanov, Muli Safra

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol "I don't know." A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ > ... more >>>

Andrej Bogdanov, Emanuele Viola

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:

\begin{enumerate}

\item a ...
more >>>

Andrej Bogdanov, Luca Trevisan

We survey the theory of average-case complexity, with a

focus on problems in NP.

Andrej Bogdanov, Luca Trevisan

We show that if an NP-complete problem has a non-adaptive

self-corrector with respect to a samplable distribution then

coNP is contained in NP/poly and the polynomial

hierarchy collapses to the third level. Feigenbaum and

Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion

under the stronger assumption that an

more >>>

Andrej Bogdanov, Luca Trevisan

We consider the problem of testing bipartiteness in the adjacency

matrix model. The best known algorithm, due to Alon and Krivelevich,

distinguishes between bipartite graphs and graphs that are

$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$

queries. We show that this is optimal for non-adaptive algorithms,

up to the ...
more >>>