Arrow Research search

Author name cluster

Andrej Bogdanov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

NeurIPS Conference 2024 Conference Paper

Towards a Scalable Reference-Free Evaluation of Generative Models

  • Azim Ospanov
  • Jingwei Zhang
  • Mohammad Jalali
  • Xuenan Cao
  • Andrej Bogdanov
  • Farzan Farnia

While standard evaluation scores for generative models are mostly reference-based, a reference-dependent assessment of generative models could be generally difficult due to the unavailability of applicable reference datasets. Recently, the reference-free entropy scores, VENDI and RKE, have been proposed to evaluate the diversity of generated data. However, estimating these scores from data leads to significant computational costs for large-scale generative models. In this work, we leverage the random Fourier features framework to reduce the metrics' complexity and propose the *Fourier-based Kernel Entropy Approximation (FKEA)* method. We utilize FKEA's approximated eigenspectrum of the kernel matrix to efficiently estimate the mentioned entropy scores. Furthermore, we show the application of FKEA's proxy eigenvectors to reveal the method's identified modes in evaluating the diversity of produced samples. We provide a stochastic implementation of the FKEA assessment algorithm with a complexity $O(n)$ linearly growing with sample size $n$. We extensively evaluate FKEA's numerical performance in application to standard image, text, and video datasets. Our empirical results indicate the method's scalability and interpretability applied to large-scale generative models. The codebase is available at [https: //github. com/aziksh-ospanov/FKEA](https: //github. com/aziksh-ospanov/FKEA).

MFCS Conference 2011 Conference Paper

Hard Functions for Low-Degree Polynomials over Prime Fields

  • Andrej Bogdanov
  • Akinori Kawachi
  • Hidetoki Tanaka

Abstract In this paper, we present a new hardness amplification for low-degree polynomials over prime fields, namely, we prove that if some function is mildly hard to approximate by any low-degree polynomials then the sum of independent copies of the function is very hard to approximate by them. This result generalizes the XOR lemma for low-degree polynomials over the binary field given by Viola and Wigderson [22]. The main technical contribution is the analysis of the Gowers norm over prime fields. For the analysis, we discuss a generalized low-degree test, which we call the Gowers test, for polynomials over prime fields, which is a natural generalization of that over the binary field given by Alon, Kaufman, Krivelevich, Litsyn and Ron [2]. This Gowers test provides a new technique to analyze the Gowers norm over prime fields. Actually, the rejection probability of the Gowers test can be analyzed in the framework of Kaufman and Sudan [17]. However, our analysis is self-contained and quantitatively better. By using our argument, we also prove the hardness of modulo functions for low-degree polynomials over prime fields.

FOCS Conference 2011 Conference Paper

Pseudorandomness for Read-Once Formulas

  • Andrej Bogdanov
  • Periklis A. 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 - Ω(1))n bits of randomness and produces an output that looks 2 -Ω(n) -pseudorandom to all such formulas. Our analysis is based on the following lemma. Let P = Mz+e, where M is the parity-check matrix of a sufficiently good binary error-correcting code of constant rate, z is a random string, e is a small-bias distribution, and all operations are modulo 2. Then for every pair of functions f, g: {0, 1} n/2 → {0, 1} and every equipartition (I, J) of [n], the distribution P is pseudorandom for the pair (f(x| I ), g(x| J )), where x| I and x| J denote the restriction of x to the coordinates in / and J, respectively. More generally, our result applies to read-once branching pro- grams of bounded width with arbitrary ordering of the inputs. We show that such branching programs are more powerful distinguishers than those that read their inputs in sequential order: There exist (explicit) pseudorandom distributions that separate these two types of branching programs.

FOCS Conference 2007 Conference Paper

Hardness Amplification for Errorless Heuristics

  • Andrej Bogdanov
  • Muli Safra

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol perp, which means "I don't know, " A central question in average-case complexity is whether every distributional decision problem in N P has an errorless heuristic scheme: This is an algorithm that, for every delta > 0, runs in time polynomial in the instance size and | / delta and answers perp only on a delta fraction of instances. We study the question from the standpoint of hardness amplification and show that If every problem in (NP, U) has errorless heuristic circuits that output the correct answer on n -2/9+omicron(1) -fraction of inputs, then (NP, U) has non-uniform errorless heuristic schemes. If every problem in (NP, U) has randomized errorless heuristic algorithms that output the correct answer on (log n) -1/10+omicron(1) -fraction of inputs, then (NP. W) has randomized errorless heuristic schemes. In both cases, the low-end amplification is achieved by analyzing a new sensitivity property of monotone boolean Junctions in NP. In the non-uniform setting we use a " holographic Junction" introduced by Benjamini, Schramm, and Wilson (STOC 2005). For the uniform setting we introduce a new Junction that can be viewed as an efficient version of Talagrand's "random DNF".

FOCS Conference 2007 Conference Paper

Pseudorandom Bits for Polynomials

  • 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 rarrF n that fool polynomials over a prime field F: (1) a generator that fools degree-2 (i. e. , quadratic) polynomials to within error 1/n, with seed length s = O(log n); (2) a generator that fools degree-3 (i. e. , cubic) polynomials to within error epsiv, with seed length s = O(Iog |F| n) + f(epsiv, F) where f depends only on epsiv and F (not on n), (3) assuming the "Gowers inverse conjecture, " for every d a generator that fools degree-d polynomials to within error epsiv, with seed length, s = O(dldrIog |F| n) + f(d, epsiv, F) where f depends only on d, epsiv, and F (not on n). We stress that the results in (1) and (2) are unconditional, i. e. do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the component-wise sum of d generators for degree-l polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i. e. , linear) polynomials (Naor and Naor; SIAM J. Comput. , 1993). In fact, over small fields such as F 2 = {0, 1}, our results constitute the first progress on these problems since the long-standing generator by Luby, Velickovic and Wigderson (ISTCS1993), whose seed length is much bigger: s = exp (Omega(radiclogn)), even for the case of degree-2 polynomials over F 2.

FOCS Conference 2003 Conference Paper

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

  • Andrej Bogdanov
  • Luca Trevisan 0001

We show that if an NP-complete problem has a non-adaptive self-corrector with respect to a distribution that can be sampled then coNP is contained in AM/poly and the polynomial hierarchy collapses to the third level. Feigenbaum and Fortnow show the same conclusion under the stronger assumption that an NP-complete problem has a non-adaptive random self-reduction. Our result shows it is impossible (using non-adaptive reductions) to base the average-case hardness of a problem in NP or the security of a one-way function on the worst-case complexity of an NP-complete problem (unless the polynomial hierarchy collapses).

FOCS Conference 2002 Conference Paper

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

  • Andrej Bogdanov
  • Kenji Obata
  • Luca Trevisan 0001

We consider the problem of testing 3-colorability in the bounded-degree model. We show that, for small enough /spl epsiv/, every tester for 3-colorability must have query complexity /spl Omega/(n). This is the first linear lower bound for testing a natural graph property in the bounded-degree model. An /spl Omega/(/spl radic/n) lower bound was previously known. For one-sided error testers, we also show an /spl Omega/(n) lower bound for testers that distinguish 3-colorable graphs from graphs that are (1/3 - /spl alpha/)-far from 3-colorable, for arbitrarily small /spl alpha/. In contrast, a polynomial time algorithm by Frieze and Jerrum (1997) distinguishes 3-colorable graphs from graphs that are 1/5-far from 3-colorable. As a by-product of our techniques, we obtain tight unconditional lower bounds on the approximation ratios achievable by sublinear time algorithms for Max E3SAT, Max E3LIN-2 and other problems.

v2026.09.13