Pages that link to "Item:Q3140018"
From MaRDI portal
The following pages link to Constant depth circuits, Fourier transform, and learnability (Q3140018):
Displaying 50 items.
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs (Q2281256) (← links)
- Prediction from partial information and hindsight, with application to circuit lower bounds (Q2311545) (← links)
- Proper learning of \(k\)-term DNF formulas from satisfying assignments (Q2323349) (← links)
- Harmonicity and invariance on slices of the Boolean cube (Q2334365) (← links)
- On the isomorphism problem for decision trees and decision lists (Q2348033) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- Bounds on the Fourier coefficients of the weighted sum function (Q2379949) (← links)
- Learning juntas in the presence of noise (Q2382279) (← links)
- On PAC learning algorithms for rich Boolean function classes (Q2382283) (← links)
- Quantitative relation between noise sensitivity and influences (Q2448963) (← links)
- Fourier analysis and large independent sets in powers of complete graphs (Q2464160) (← links)
- On extremal \(k\)-CNF formulas (Q2509734) (← links)
- Efficient learning algorithms yield circuit lower bounds (Q2517822) (← links)
- Learning DNF from random walks (Q2568457) (← links)
- Alternation, sparsity and sensitivity: bounds and exponential gaps (Q2632012) (← links)
- Exact learning from an honest teacher that answers membership queries (Q2636406) (← links)
- A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions (Q2681684) (← links)
- BKW meets Fourier new algorithms for LPN with sparse parities (Q2697880) (← links)
- Homomorphic Evaluation Requires Depth (Q2796133) (← links)
- Fine-Grained Cryptography (Q2829959) (← links)
- Learning $$AC^0$$ Under k-Dependent Distributions (Q2988821) (← links)
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates (Q3012933) (← links)
- Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity (Q3088135) (← links)
- On (Not) Computing the Möbius Function Using Bounded Depth Circuits (Q3168449) (← links)
- Fast Pseudorandom Functions Based on Expander Graphs (Q3179351) (← links)
- Approximating Boolean Functions with Depth-2 Circuits (Q3451753) (← links)
- The learnability of quantum states (Q3508097) (← links)
- Decision Trees and Influences of Variables Over Product Probability Spaces (Q3557496) (← links)
- Testing monotone high‐dimensional distributions (Q3608311) (← links)
- Variable Influences in Conjunctive Normal Forms (Q3637162) (← links)
- Ehrenfeucht-Fraïssé Games on Random Structures (Q3638295) (← links)
- Average-Case Lower Bounds for Noisy Boolean Decision Trees (Q4210156) (← links)
- Submodular Functions: Learnability, Structure, and Optimization (Q4564777) (← links)
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits (Q4568115) (← links)
- On polynomial approximations to AC (Q4633319) (← links)
- What Circuit Classes Can Be Learned with Non-Trivial Savings? (Q4638080) (← links)
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem (Q4957916) (← links)
- Quantum Hardness of Learning Shallow Classical Circuits (Q4994987) (← links)
- Agnostic Learning from Tolerant Natural Proofs (Q5002638) (← links)
- (Q5009532) (← links)
- Pseudo-Derandomizing Learning and Approximation (Q5009554) (← links)
- Pseudorandom Functions: Three Decades Later (Q5021131) (← links)
- On small depth threshold circuits (Q5056127) (← links)
- (Q5077146) (← links)
- Expander-Based Cryptography Meets Natural Proofs (Q5090391) (← links)
- Criticality of regular formulas (Q5091751) (← links)
- (Q5121889) (← links)
- Agnostically Learning Boolean Functions with Finite Polynomial Representation (Q5136248) (← links)
- Sums with the Möbius function twisted by characters with powerful moduli (Q5206259) (← links)
- On the nonlinearity of the sequence of signs of Kloosterman sums (Q5315950) (← links)
