Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Tail Bound for Read-k Families of Functions
103
0
0.0
(
0
)
Added by
Dmitry Gavinsky
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,...,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,...,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,...,Y_r$.
rate research
Read More
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : {0,1}^n to {0,1}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph theory, and statistical physics, to Gaussian geometry, metric/Banach spaces, and social choice theory. The intent of this book is both to develop the foundations of the field and to give a wide (though far from exhaustive) overview of its applications. Each chapter ends with a highlight showing the power of analysis of Boolean functions in different subject areas: property testing, social choice, cryptography, circuit complexity, learning theory, pseudorandomness, hardness of approximation, concrete complexity, and random graph theory. The book can be used as a reference for working researchers or as the basis of a one-semester graduate-level course. The author has twice taught such a course at Carnegie Mellon University, attended mainly by graduate students in computer science and mathematics but also by advanced undergraduates, postdocs, and researchers in adjacent fields. In both years most of Chapters 1-5 and 7 were covered, along with parts of Chapters 6, 8, 9, and 11, and some additional material on additive combinatorics. Nearly 500 exercises are provided at the ends of the books chapters.
We apply down operators in the affine nilCoxeter algebra to yield explicit combinatorial expansions for certain families of non-commutative k-Schur functions. This yields a combinatorial interpretation for a new family of k-Littlewood-Richardson coefficients.
The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(frac{n}{log n})$ players can bias the outcome of any Boolean function ${0,1}^n to {0,1}$ with respect to the uniform measure. We extend their result to arbitrary product measures on ${0,1}^n$, by combining their argument with a completely different argument that handles very biased coordinates. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube $[0,1]^n$ (or, equivalently, on ${1,dots,n}^n$) can be biased using coalitions of $o(n)$ players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is $o(log^* n)$, a coalition of $o(n)$ players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on ${0,1}^n$. The argument of Russell et al. relies on the fact that a coalition of $o(n)$ players can boost the expectation of any Boolean function from $epsilon$ to $1-epsilon$ with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to $mu_{1-1/n}$ shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.
A famous conjecture of Gyarfas and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results.
Let $(S,mathcal L)$ be a smooth, irreducible, projective, complex surface, polarized by a very ample line bundle $mathcal L$ of degree $d > 35$. In this paper we prove that $K^2_Sgeq -d(d-6)$. The bound is sharp, and $K^2_S=-d(d-6)$ if and only if $d$ is even, the linear system $|H^0(S,mathcal L)|$ embeds $S$ in a smooth rational normal scroll $Tsubset mathbb P^5$ of dimension $3$, and here, as a divisor, $S$ is linearly equivalent to $frac{d}{2}Q$, where $Q$ is a quadric on $T$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
