KKL, Kruskal-Katona, and Monotone Nets

No abstract is available for this paper.

• Publication year

  2009

• Venue

  2009 50th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2009-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/100787325
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A theorem of finite sets

  2009cited by this paper
• Shadows and intersections: Stability and new proofs

  2008cited by this paper
• Buy-at-Bulk Network Design with Protection

  2007cited by this paper
• Improved lower bounds for embeddings into L1

  2006cited by this paper
• Expander Graphs and their Applications

  2006cited by this paper
• Integrality gaps for sparsest cut and minimum linear arrangement problems

  2006cited by this paper
• On learning monotone Boolean functions under the uniform distribution

  2006influential reference
• Learning monotone decision trees in polynomial time

  2006cited by this paper
• On the hardness of approximating minimum vertex cover

  2005cited by this paper
• Influence and sharp-threshold theorems for monotonic measures

  2005cited by this paper
• ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT

  2005cited by this paper
• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality

  2005cited by this paper
• Edge-Isoperimetric Inequalities and Influences

  2005cited by this paper
• Vertex cover might be hard to approximate to within 2-/spl epsiv/

  2003cited by this paper
• Deterministic extractors for bit-fixing sources and exposure-resilient cryptography

  2003cited by this paper
• DETERMINISTIC EXTRACTORS FOR BIT-FIXING SOURCES AND EXPOSURE-RESILIENT CRYPTOGRAPHY

  2003cited by this paper
• On the log-Sobolev constant for the simple random walk on the n-cycle: the even cases

  2003cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• On learning monotone Boolean functions

  1998influential reference
• Noise sensitivity of Boolean functions and applications to percolation

  1998influential reference
• Boolean Functions With Low Average Sensitivity Depend On Few Coordinates

  1998cited by this paper
• Logarithmic Sobolev inequality for some models of random walks

  1998influential reference
• On the Fourier spectrum of monotone functions

  1996cited by this paper
• Every monotone graph property has a sharp threshold

  1996cited by this paper
• LOGARITHMIC SOBOLEV INEQUALITIES FOR FINITE MARKOV CHAINS

  1996influential reference
• Fourier analysis for probabilistic communication complexity

  1995cited by this paper
• Cryptographic limitations on learning Boolean formulae and finite automata

  1994cited by this paper
• On Russo's Approximate Zero-One Law

  1994influential reference
• The influence of variables in product spaces

  1992cited by this paper
• Collective Coin Flipping

  1989influential reference
• Crytographic limitations on learning Boolean formulae and finite automata

  1989cited by this paper
• The influence of variables on Boolean functions

  1988influential reference
• Time to reach stationarity in the Bernoulli-Laplace diffusion model

  1987cited by this paper
• Threshold functions

  1987cited by this paper
• An approximate zero-one law

  1982cited by this paper
• Generating a random permutation with random transpositions

  1981influential reference
• Combinatorial problems and exercises

  1979cited by this paper
• Every connected regular graph of even degree is a Schreier coset graph

  1977cited by this paper
• An Introduction to Probability Theory and Its Applications; Vol. 1

  1969cited by this paper
• An introduction to probability theory and its applications, Vol. II: by William Feller. 626 pages, 6 × 9 inches, New York, John Wiley and Sons, Inc., 1966. Price $12.00

  1967cited by this paper
• An Introduction to Probability Theory and Its Applications

  1967cited by this paper
• Families of Non-disjoint subsets*

  1966cited by this paper
• An Introduction to Probability Theory and Its Applications

  1959cited by this paper

• Quantum Talagrand-type Inequalities via Variance Decay

  2026cites this paper
• A Near-Optimal Polynomial Distance Lemma over Boolean Slices

  2025cites this paper
• The Probably Approximately Correct Learning Model in Computational Learning Theory

  2025cites this paper
• On Exact Learning of d-Monotone Functions

  2025cites this paper
• Functional L1-L Inequalities in the CAR Algebra

  2024cites this paper
• Query complexity of Boolean functions on the middle slice of the cube

  2023cites this paper
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier

  2023cites this paper
• Influences in Mixing Measures

  2023cites this paper
• New Distinguishers for Negation-Limited Weak Pseudorandom Functions

  2022cites this paper
• Complexity measures on the symmetric group and beyond

  2022cites this paper
• Improved Monotonicity Testers via Hypercube Embeddings

  2022cites this paper
• An OSSS-type inequality for uniformly drawn subsets of fixed size

  2022influential citation
• Quantum Talagrand, KKL and Friedgut’s Theorems and the Learnability of Quantum Boolean Functions

  2022influential citation
• Properly learning monotone functions via local correction

  2022cites this paper
• Query complexity of Boolean functions on slices

  2022cites this paper
• Weak learning convex sets under normal distributions

  2021cites this paper
• Convex Influences

  2021influential citation
• Hypercontractivity on high dimensional expanders

  2021cites this paper
• Hypercontractivity on the symmetric group

  2020cites this paper
• Provable guarantees for decision tree induction: the agnostic setting

  2020cites this paper
• Diversity

  2020cites this paper
• Complexity Measures on the Symmetric Group and Beyond

  2020cites this paper
• Kruskal-Katona for convex sets, with applications

  2019cites this paper
• A structure theorem for almost low-degree functions on the slice

  2019cites this paper
• Top-down induction of decision trees: rigorous guarantees and inherent limitations

  2019cites this paper
• Finitary Boolean functions

  2019cites this paper
• Boolean Function Analysis on High-Dimensional Expanders

  2018influential citation
• Boolean functions on high-dimensional expanders

  2018cites this paper
• A log-Sobolev inequality for the multislice, with applications

  2018influential citation
• Boolean degree 1 functions on some classical association schemes

  2018cites this paper
• Stability for vertex isoperimetry in the cube

  2018influential citation
• C C ] 3 0 O ct 2 01 4 Learning circuits with few negations

  2018cites this paper
• 1 N ov 2 01 7 Biased Halfspaces , Noise Sensitivity , and Local Chernoff Inequalities ( Extended Version )

  2017influential citation
• An unified approach to the Junta theorem for discrete and continuous models

  2017cites this paper
• Biased halfspaces, noise sensitivity, and relative Chernoff inequalities (extended version)

  2017cites this paper
• Biased halfspaces, noise sensitivity, and local Chernoff inequalities

  2017influential citation
• Testing k-Monotonicity

  2016cites this paper
• Agnostic Learning in Permutation-Invariant Domains

  2016cites this paper
• A Noise Sensitivity Theorem for Schreier Graphs

  2015cites this paper
• Unconditional Lower Bounds in Complexity Theory

  2015cites this paper
• Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

  2015cites this paper
• Direct Sum Testing

  2015cites this paper
• Correlation Bounds Against Monotone NC^1

  2015cites this paper
• On the Converse of Talagrand's Influence Inequality

  2015cites this paper
• The Power of Negations in Cryptography

  2015cites this paper
• The Kruskal − Katona Function, Conway Sequence, Takagi Curve, and Pascal Adic

  2014cites this paper
• Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube

  2014cites this paper
• Approximate resilience, monotonicity, and the complexity of agnostic learning

  2014cites this paper
• Learning circuits with few negations

  2014cites this paper
• An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube

  2014cites this paper
• Analytic Methods in Concrete Complexity

  2014cites this paper
• Low Influence Functions over Slices of the Boolean Hypercube Depend on Few Coordinates

  2014cites this paper
• On Quantitative Noise Stability and Influences for Discrete and Continuous Models

  2014influential citation
• Average Case Lower Bounds for Monotone Switching Networks

  2013cites this paper
• Sharpness of KKL on Schreier graphs

  2013cites this paper
• Testing properties of boolean functions

  2012cites this paper
• On derandomization and average-case complexity of monotone functions

  2012cites this paper
• Hypercontractivity and its applications

  2011cites this paper
• Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

  2011cites this paper
• Hypercontractive measures, Talagrand's inequality, and influences

  2011influential citation
• Computational Bottlenecks for Evolvability

  2011cites this paper
• Computational Bottlenecks for Evolvability Varun Kanade

  2011cites this paper
• Cuts in Cartesian Products of Graphs

  2011cites this paper
• Agnostically Learning under Permutation Invariant Distributions

  2010cites this paper
• Learning, cryptography, and the average case

  2010cites this paper
• Deterministic simulations and hierarchy theorems for randomized algorithms

  2010cites this paper
• On the learnability of monotone functions

  2009cites this paper
• Shadows of ordered graphs

  2009cites this paper