Testing Fourier Dimensionality and Sparsity

No abstract is available for this paper.

• Publication year

  2009

• Venue

  SIAM journal on computing (Print)

• Publication date

  2009-07-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/100785429
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The mixing time of Glauber dynamics for coloring regular trees

  2010cited by this paper
• Testing Halfspaces

  2009cited by this paper
• List-decoding reed-muller codes over small fields

  2008cited by this paper
• Algebraic property testing: the role of invariance

  2008cited by this paper
• Improved Bounds for Testing Juntas

  2008cited by this paper
• Testing for Concise Representations

  2007influential reference
• Sparse Random Linear Codes are Locally Decodable and Testable

  2007cited by this paper
• Simulating Quantum Correlations with Finite Communication

  2007cited by this paper
• A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

  2006cited by this paper
• New Results for Learning Noisy Parities and Halfspaces

  2006influential reference
• Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting

  2006cited by this paper
• A combinatorial characterization of the testable graph properties: it's all about regularity

  2006cited by this paper
• Low-degree tests at large distances

  2006cited by this paper
• A characterization of the (natural) graph properties testable with one-sided error

  2005cited by this paper
• Every monotone graph property is testable

  2005cited by this paper
• Testing Reed-Muller codes

  2005cited by this paper
• THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING

  2004cited by this paper
• Testing Low-Degree Polynomials over GF(2(

  2003cited by this paper
• Testing Basic Boolean Formulae

  2002cited by this paper
• Quantum property testing

  2002cited by this paper
• Testing Juntas

  2002cited by this paper
• Complexity measures and decision tree complexity: a survey

  2002cited by this paper
• A Review of Graph Grammars and Preview of ICGT 2002: The First International Conference on Graph Transformation.

  2001cited by this paper
• Random Vectors of Bounded Weight and Their Linear Dependencies

  2000cited by this paper
• Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem

  1999cited by this paper
• Free bits, PCPs and non-approximability-towards tight results

  1995cited by this paper
• Linearity testing in characteristic two

  1995cited by this paper
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution

  1994cited by this paper
• Learning decision trees using the Fourier spectrum

  1991cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989cited by this paper

• Testing Isomorphism of Boolean Functions over Finite Abelian Groups

  2025cites this paper
• Query-Optimal Estimation of Unitary Channels via Pauli Dimensionality

  2025cites this paper
• Structure of sparse Boolean functions over Abelian groups, and its application to testing

  2024influential citation
• On the Power of Interactive Proofs for Learning

  2024cites this paper
• Hamiltonian Property Testing

  2024cites this paper
• Testing and Learning Structured Quantum Hamiltonians

  2024cites this paper
• Extracting Formulae in Many-Valued Logic From Deep Neural Networks

  2024cites this paper
• Testing Self-Reducible Samplers

  2023cites this paper
• Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

  2023cites this paper
• Classical Verification of Quantum Learning

  2023cites this paper
• On the Role of Entanglement and Statistics in Learning

  2023cites this paper
• A Study of Sparse Representation of Boolean Functions

  2023cites this paper
• One-Way Communication Complexity of Partial XOR Functions

  2023cites this paper
• Testing of Index-Invariant Properties in the Huge Object Model

  2022cites this paper
• Learning Versus Pseudorandom Generators in Constant Parallel Time

  2022cites this paper
• Hardening Circuit-Design IP Against Reverse-Engineering Attacks

  2022cites this paper
• A Generalization of a Theorem of Rothschild and van Lint

  2021cites this paper
• Tight Chang's-lemma-type bounds for Boolean functions

  2020cites this paper
• On the Decision Tree Complexity of Threshold Functions

  2020cites this paper
• An Optimal Tester for $k$-Linear

  2020cites this paper
• Power of Decision Trees with Monotone Queries

  2020cites this paper
• Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms

  2019cites this paper
• Almost Optimal Testers for Concise Representations

  2019cites this paper
• Almost optimal distribution-free junta testing

  2019cites this paper
• Fast Fourier Sparsity Testing

  2019cites this paper
• Higher-order Fourier Analysis and Applications

  2019cites this paper
• J an 2 01 9 Almost Optimal Distribution-free Junta Testing

  2019cites this paper
• Quantum algorithms and learning theory

  2018cites this paper
• Distribution-free junta testing

  2018cites this paper
• Periodic Fourier representation of Boolean functions

  2018cites this paper
• Linear Sketching over F_2

  2018cites this paper
• Sensitivity, Affine Transforms and Quantum Communication Complexity

  2018cites this paper
• Two new results about quantum exact learning

  2018cites this paper
• Parity Decision Tree Complexity is Greater Than Granularity

  2018cites this paper
• Is your function low dimensional?

  2018cites this paper
• Is your data low-dimensional?

  2018cites this paper
• Settling the Query Complexity of Non-adaptive Junta Testing

  2017cites this paper
• 1 1 N ov 2 01 6 Linear Sketching over F 2

  2016cites this paper
• Structure of Protocols for XOR Functions

  2016cites this paper
• Linear Sketching over $\mathbb F_2$

  2016cites this paper
• Testing Submodularity and Other Properties of Valuation Functions

  2016cites this paper
• On Higher-Order Fourier Analysis over Non-Prime Fields

  2016cites this paper
• On the Efficiency of the Probabilistic Neutral Bits Method in Statistical Cryptanalysis of Synchronous Stream Ciphers

  2016cites this paper
• Sparse Polynomial Interpolation and Testing

  2016cites this paper
• Improved Upper Bound for the Relative Distance Between a Boolean Function and the Set of k-Dimensional Functions

  2015cites this paper
• Fourier Sparsity of GF(2) Polynomials

  2015cites this paper
• альный выбор, альтернативные варианты оптимиза- ции, фаззер, система защиты. SYSTEM ANALYSIS OF MULTICRITERION OPTIMIZATION PROBLEM FOR INFORMATION SYSTEM PROTECTION (HACKING)

  2015cites this paper
• On the Power of Parity Queries in Boolean Decision Trees

  2015cites this paper
• Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity

  2015cites this paper
• The List-Decoding Size of Fourier-Sparse Boolean Functions

  2015cites this paper
• Adaptivity Helps for Testing Juntas

  2015cites this paper
• Using higher-order Fourier analysis over general fields

  2015cites this paper
• Algebraically Degenerate Approximations of Boolean Functions

  2014cites this paper
• Gowers Norm, Function Limits, and Parameter Estimation

  2014influential citation
• Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

  2014cites this paper
• A characterization of locally testable affine-invariant properties via decomposition theorems

  2014cites this paper
• Analysis of Boolean Functions

  2014cites this paper
• On The Structure of Boolean Functions with Small Spectral Norm

  2014cites this paper
• Algebraically Degenerate Approximations of Boolean Functions

  2014cites this paper
• On testing affine-invariant properties over finite fields ∗

  2013cites this paper
• Query Complexity of Matroids

  2013cites this paper
• On the Structure of Boolean Functions with Small Spectral Norm

  2013cites this paper
• An improved test of Boolean functions for k-dimensionality

  2013influential citation
• Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture

  2013influential citation
• Tight Lower Bounds for Testing Linear Isomorphism

  2013influential citation
• Gems in decision tree complexity revisited

  2013cites this paper
• Sketching via hashing: from heavy hitters to compressed sensing to sparse fourier transform

  2013cites this paper
• Testing Linear-Invariant Function Isomorphism

  2013influential citation
• Estimating the Distance from Testable Affine-Invariant Properties

  2013cites this paper
• Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities

  2013cites this paper
• Guest column: on testing affine-invariant properties over finite fields

  2013cites this paper
• Testing Booleanity and the Uncertainty Principle

  2012cites this paper
• Every locally characterized affine-invariant property is testable

  2012cites this paper
• On the Semantics of Local Characterizations for Linear-Invariant Properties ∗

  2012cites this paper
• Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching

  2012cites this paper
• Query-efficient computation in property testing and learning theory

  2012cites this paper
• Efficient Sample Extractors for Juntas with Applications

  2011cites this paper
• Testability of linear-invariant properties

  2011cites this paper
• Quantum algorithm for the Boolean hidden shift problem

  2011cites this paper
• Algebraic Property Testing

  2011cites this paper
• A Canonical Form for Testing Boolean Function Properties

  2011cites this paper
• On the Semantics of Local Characterizations for Linear-Invariant Properties

  2011cites this paper
• Framework for Testing Linear-Invariant Properties

  2011cites this paper
• Testing Odd-Cycle-Freeness in Boolean Functions

  2011cites this paper
• Property testing on boolean functions Thesis proposal

  2010cites this paper
• Invariance in Property Testing

  2010cites this paper
• A Fourier-Analytic Approach to Reed–Muller Decoding

  2010cites this paper
• Property Testing via Set-Theoretic Operations

  2010cites this paper
• Testing by Implicit Learning: A Brief Survey

  2010cites this paper
• A Unified Framework for Testing Linear-Invariant Properties

  2010cites this paper
• New Results for Random Walk Learning

  2009cites this paper
• On the communication complexity of XOR functions

  2009cites this paper
• A Unified Framework for Testing Linear-Invariant Properties

  year unknowncites this paper