We define and study an extension of the notion of the VC-dimension of a hypergraph and apply it to establish a Tverberg type theorem for unions of convex sets. We also prove a new Radon type theorem for unions of convex sets and settle a well-known open problem posed by Kalai in the 1970s.

We investigate prophet inequalities with competitive ratios approaching 1, seeking to generalize k-uniform matroids. We first show that large girth does not suffice: for all k, there exists a matroid of girth ≥ k and a prophet inequality instance on that matroid whose optimal competitive ratio is 1/2. Next, we show k-fold matroid unions do suffice: we provide a prophet inequality with competitive ratio 1-O(√{(log k)/k}) for any k-fold matroid union. Our prophet inequality follows from an online contention resolution scheme. The key technical ingredient in our online contention resolution scheme is a novel bicriterion concentration inequality for arbitrary monotone 1-Lipschitz functions over independent items which may be of independent interest. Applied to our particular setting, our bicriterion concentration inequality yields "Chernoff-strength" concentration for a 1-Lipschitz function that is not (approximately) self-bounding.

Abstract. A subset [Formula: see text] of the Boolean hypercube [Formula: see text] is a sumset if [Formula: see text] for some [Formula: see text]. We prove that the number of sumsets in [Formula: see text] is asymptotically [Formula: see text]. Furthermore, we show that the family of sumsets in [Formula: see text] is almost identical to the family of all subsets of [Formula: see text] that contain a complete linear subspace of codimension 1.

We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. Its vertices are realizable datasets and two datasets $S,S’$ are connected by an edge if they contradict each other (i.e., there is a point $x$ that is labeled differently in $S$ and $S’$). Our main finding is that the combinatorial structure of $G$ is deeply related to learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under approximate DP is captured by the clique number of $G$. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the \emph{clique dimension} and \emph{fractional clique dimension}. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.

Contrastive learning is a highly successful technique for learning representations of data from labeled tuples, specifying the distance relations within the tuple. We study the sample complexity of contrastive learning, i.e. the minimum number of labeled tuples sufficient for getting high generalization accuracy. We give tight bounds on the sample complexity in a variety of settings, focusing on arbitrary distance functions, $\ell_p$-distances, and tree metrics. Our main result is an (almost) optimal bound on the sample complexity of learning $\ell_p$-distances for integer $p$. For any $p \ge 1$, we show that $\tilde \Theta(nd)$ labeled tuples are necessary and sufficient for learning $d$-dimensional representations of $n$-point datasets. Our results hold for an arbitrary distribution of the input samples and are based on giving the corresponding bounds on the Vapnik-Chervonenkis/Natarajan dimension of the associated problems. We further show that the theoretical bounds on sample complexity obtained via VC/Natarajan dimension can have strong predictive power for experimental results, in contrast with the folklore belief about a substantial gap between the statistical learning theory and the practice of deep learning.

Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, which is clearly also a lower bound in the worst case. However, several works have shown how to solve this problem in sublinear time in expectation when the input graph is drawn from one of several classes of random graphs. In this work, we extend these results by giving sublinear time shortest path (and short path) algorithms for expander graphs. We thus identify a natural deterministic property of a graph (that is satisfied by typical random regular graphs) which suffices for sublinear time shortest paths. The algorithms are very simple, involving only bidirectional breadth first search and short random walks. We also complement our new algorithms by near-matching lower bounds.

Abstract. We correct an error in the appendix of [N. Alon et al., SIAM J. Discrete Math., 34 (2020), pp. 885–903] and prove that it is NP-hard to approximate the size of a maximum induced matching of a bipartite graph within any constant factor.

Abstract. It is known that any open necklace with beads of [Formula: see text] types, in which the number of beads of each type is divisible by [Formula: see text], can be partitioned by at most [Formula: see text] cuts into intervals that can be distributed into [Formula: see text] collections, each containing the same number of beads of each type. This is tight for all values of [Formula: see text] and [Formula: see text]. Here, we consider the case of random necklaces, where the number of beads of each type is [Formula: see text]. Then the minimum number of cuts required for a “fair” partition with the above property is a random variable [Formula: see text]. We prove that for fixed [Formula: see text] and large [Formula: see text], this random variable is at least [Formula: see text] with high probability. For [Formula: see text], fixed [Formula: see text], and large [Formula: see text], we determine the asymptotic behavior of the probability that [Formula: see text] for all values of [Formula: see text]. We show that this probability is polynomially small when [Formula: see text], is bounded away from zero when [Formula: see text], and decays like [Formula: see text] when [Formula: see text]. We also show that for large [Formula: see text], [Formula: see text] is at most [Formula: see text] with high probability and that for large [Formula: see text] and large ratio [Formula: see text], [Formula: see text] is [Formula: see text] with high probability.

Abstract. For an oriented graph [Formula: see text] and a set [Formula: see text], the inversion of [Formula: see text] in [Formula: see text] is the digraph obtained by reversing the orientations of the edges of [Formula: see text] with both endpoints in [Formula: see text]. The inversion number of [Formula: see text], [Formula: see text], is the minimum number of inversions which can be applied in turn to [Formula: see text] to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet we show that, for each [Formula: see text] and tournament [Formula: see text], the problem of deciding whether [Formula: see text] is solvable in time [Formula: see text], which is tight for all [Formula: see text]. In particular, the problem is fixed-parameter tractable when parameterized by [Formula: see text]. On the other hand, we build on their work to prove their conjecture that for [Formula: see text] the problem of deciding whether a general oriented graph [Formula: see text] has [Formula: see text] is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called dijoin digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an [Formula: see text]-vertex tournament is [Formula: see text].

The deletion distance between two binary words$u,v \in \{0,1\}^{n}$is the smallest$k$such that$u$and$v$share a common subsequence of length$n-k$. A set$C$of binary words of length$n$is called a$k$-deletion code if every pair of distinct words in$C$has deletion distance greater than$k$. In 1965, Levenshtein initiated the study of deletion codes by showing that, for$k\ge 1$fixed and$n$going to infinity, a$k$-deletion code$C\subseteq \{0,1\}^{n}$of maximum size satisfies$\Omega _{k}(2^{n}/n^{2k}) \leq |C| \leq O_{k}(2^{n}/n^{k})$. We make the first asymptotic improvement to these bounds by showing that there exist$k$-deletion codes with size at least$\Omega _{k}(2^{n} \log n/n^{2k})$. Our proof is inspired by Jiang and Vardy’s improvement to the classical Gilbert–Varshamov bounds. We also establish several related results on the number of longest common subsequences and shortest common supersequences of a pair of words with given length and deletion distance.

The existence of EFX allocations is a fundamental open problem in discrete fair division. Since the general problem has been elusive, progress is made on two fronts: (i) proving existence when the number of agents is small, and (ii) proving the existence of relaxations of EFX. In this paper, we improve and simplify the state-of-the-art results on both fronts with new techniques.

Abstract. Lionel Levine’s hat challenge has [Formula: see text] players, each with a (very large or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine’s conjecture is that the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to problems in graph theory: relating the size of the largest independent set in a graph and in a random induced subgraph of it, and bounding the size of a set of vertices intersecting every maximum-size independent set in a graph.

Abstract. We investigate the maximum size of graph families on a common vertex set of cardinality [Formula: see text] such that the symmetric difference of the edge sets of any two members of the family satisfies some prescribed condition. We solve the problem completely for infinitely many values of [Formula: see text] when the prescribed condition is connectivity or 2-connectivity, Hamiltonicity, or the containment of a spanning star. We also investigate local conditions that can be certified by looking at only a subset of the vertex set. In these cases a capacity-type asymptotic invariant is defined and when the condition is to contain a certain subgraph this invariant is shown to be a simple function of the chromatic number of this required subgraph. This is proven using classical results from extremal graph theory. Several variants are considered and the paper ends with a collection of open problems.

We study a natural generalization of the classical $\epsilon$-net problem (Haussler--Welzl 1987), which we call the "$\epsilon$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $\epsilon\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $\epsilon n$ contains a set in $S$. When $t=1$, this corresponds to the $\epsilon$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $\epsilon$-$t$-net of size $O(\frac{ (1+\log t)d}{\epsilon} \log \frac{1}{\epsilon})$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}{\epsilon})$-sized $\epsilon$-$t$-nets. We also present an explicit construction of $\epsilon$-$t$-nets (including $\epsilon$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $\epsilon$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

Let H be a binary-labeled concept class. We prove that H can be PAC learned by an (approximate) differentially private algorithm if and only if it has a finite Littlestone dimension. This implies a qualitative equivalence between online learnability and private PAC learnability.

We extend the classical theory of PAC learning in a way which allows to model a rich variety of practical learning tasks where the data satisfy special properties that ease the learning process. For example, tasks where the distance of the data from the decision boundary is bounded away from zero, or tasks where the data lie on a lower dimensional surface. The basic and simple idea is to consider partial concepts: these are functions that can be undefined on certain parts of the space. When learning a partial concept, we assume that the source distribution is supported only on points where the partial concept is defined. This way, one can naturally express assumptions on the data such as lying on a lower dimensional surface, or that it satisfies margin conditions. In contrast, it is not at all clear that such assumptions can be expressed by the traditional PAC theory using learnable total concept classes, and in fact we exhibit easy-to-learn partial concept classes which provably cannot be captured by the traditional PAC theory. This also resolves, in a strong negative sense, a question posed by Attias, Kontorovich, and Mansour (2019). We characterize PAC learnability of partial concept classes and reveal an algorithmic landscape which is fundamentally different than the classical one. For example, in the classical PAC model, learning boils down to Empirical Risk Minimization (ERM). This basic principle follows from Uniform Convergence and the Fundamental Theorem of PAC Learning (Vapnik and Chervonenkis, 1971, 1974b; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989; Hodges, 1993). In stark contrast, we show that the ERM principle fails spectacularly in explaining learnability of partial concept classes. In fact, we demonstrate classes that are incredibly easy to learn, but such that any algorithm that learns them must use an hypothesis space with unbounded VC dimension. We also find that the sample compression conjecture of Littlestone and Warmuth fails in this setting. Our impossibility results hinge on the recent breakthroughs in communication complexity and graph theory by Göös (2015); Ben-David, Hatami, and Tal (2017); Balodis, Ben-David, Göös, Jain, and Kothari (2021). Thus, this theory features problems that cannot be represented in the traditional way and cannot be solved in the traditional way. We view this as evidence that it might provide insights on the nature of learnability in realistic scenarios which the classical theory fails to explain. We include in the paper suggestions for future research and open problems in several contexts, including combinatorics, geometry, and learning theory.

We provide approximation algorithms for two problems, known as NECKLACE SPLITTING and $ε$-CONSENSUS SPLITTING. In the problem $ε$-CONSENSUS SPLITTING, there are $n$ non-atomic probability measures on the interval $[0, 1]$ and $k$ agents. The goal is to divide the interval, via at most $n (k-1)$ cuts, into pieces and distribute them to the $k$ agents in an approximately equitable way, so that the discrepancy between the shares of any two agents, according to each measure, is at most $2 ε/ k$. It is known that this is possible even for $ε= 0$. NECKLACE SPLITTING is a discrete version of $ε$-CONSENSUS SPLITTING. For $k = 2$ and some absolute positive constant $ε$, both of these problems are PPAD-hard. We consider two types of approximation. The first provides every agent a positive amount of measure of each type under the constraint of making at most $n (k - 1)$ cuts. The second obtains an approximately equitable split with as few cuts as possible. Apart from the offline model, we consider the online model as well, where the interval (or necklace) is presented as a stream, and decisions about cutting and distributing must be made on the spot. For the first type of approximation, we describe an efficient algorithm that gives every agent at least $\frac{1}{nk}$ of each measure and works even online. For the second type of approximation, we provide an efficient online algorithm that makes $\text{poly}(n, k, ε)$ cuts and an offline algorithm making $O(nk \log \frac{k}ε)$ cuts. We also establish lower bounds for the number of cuts required in the online model for both problems even for $k=2$ agents, showing that the number of cuts in our online algorithm is optimal up to a logarithmic factor.

Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are online learnable. Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of Littlestone’s dimension, thus resolving the main open question from Ben-David, Pál, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).

Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are "rules-of-thumbs" from an "easy-to-learn class". (Schapire and Freund~'12, Shalev-Shwartz and Ben-David '14.) Formally, we assume the class of weak hypotheses has a bounded VC dimension. We focus on two main questions: (i) Oracle Complexity: How many weak hypotheses are needed to produce an accurate hypothesis? We design a novel boosting algorithm and demonstrate that it circumvents a classical lower bound by Freund and Schapire ('95, '12). Whereas the lower bound shows that $\Omega({1}/{\gamma^2})$ weak hypotheses with $\gamma$-margin are sometimes necessary, our new method requires only $\tilde{O}({1}/{\gamma})$ weak hypothesis, provided that they belong to a class of bounded VC dimension. Unlike previous boosting algorithms which aggregate the weak hypotheses by majority votes, the new boosting algorithm uses more complex ("deeper") aggregation rules. We complement this result by showing that complex aggregation rules are in fact necessary to circumvent the aforementioned lower bound. (ii) Expressivity: Which tasks can be learned by boosting weak hypotheses from a bounded VC class? Can complex concepts that are "far away" from the class be learned? Towards answering the first question we {introduce combinatorial-geometric parameters which capture expressivity in boosting.} As a corollary we provide an affirmative answer to the second question for well-studied classes, including half-spaces and decision stumps. Along the way, we establish and exploit connections with Discrepancy Theory.

A recent palette sparsification theorem of Assadi, Chen, and Khanna [SODA'19] states that in every n-vertex graph G with maximum degree Δ, sampling O(log n) colors per each vertex independently from Δ+1 colors almost certainly allows for proper coloring of G from the sampled colors. Besides being a combinatorial statement of its own independent interest, this theorem was shown to have various applications to design of algorithms for (Δ+1) coloring in different models of computation on massive graphs such as streaming or sublinear-time algorithms. In this paper, we focus on palette sparsification beyond (Δ+1) coloring, in both regimes when the number of available colors is much larger than (Δ+1), and when it is much smaller. In particular, - We prove that for (1+ε) Δ coloring, sampling only O_ε(√{log n}) colors per vertex is sufficient and necessary to obtain a proper coloring from the sampled colors - this shows a separation between (1+ε) Δ and (Δ+1) coloring in the context of palette sparsification. - A natural family of graphs with chromatic number much smaller than (Δ+1) are triangle-free graphs which are O(Δ/ln Δ) colorable. We prove a palette sparsification theorem tailored to these graphs: Sampling O(Δ^γ + √{log n}) colors per vertex is sufficient and necessary to obtain a proper O_γ(Δ/ln Δ) coloring of triangle-free graphs. - We also consider the "local version" of graph coloring where every vertex v can only be colored from a list of colors with size proportional to the degree deg(v) of v. We show that sampling O_ε(log n) colors per vertex is sufficient for proper coloring of any graph with high probability whenever each vertex is sampling from a list of (1+ε) ⋅ deg(v) arbitrary colors, or even only deg(v)+1 colors when the lists are the sets {1,…,deg(v)+1}. Our new palette sparsification results naturally lead to a host of new and/or improved algorithms for vertex coloring in different models including streaming and sublinear-time algorithms.

Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Cite this Paper BibTeX @InProceedings{pmlr-v125-alon20b, title = {Hierarchical Clustering: A 0.585 Revenue Approximation}, author = {Alon, Noga and Azar, Yossi and Vainstein, Danny}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {153--162}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/alon20b/alon20b.pdf}, url = {https://proceedings.mlr.press/v125/alon20b.html}, abstract = { Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Copy to Clipboard Download Endnote %0 Conference Paper %T Hierarchical Clustering: A 0.585 Revenue Approximation %A Noga Alon %A Yossi Azar %A Danny Vainstein %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-alon20b %I PMLR %P 153--162 %U https://proceedings.mlr.press/v125/alon20b.html %V 125 %X Hierarchical Clustering trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16’) initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17’) dubbing it the Revenue goal function. In this problem, given a nonnegative weight $w_{ij}$ for each pair $i,j \in [n]=\{1,2, \ldots ,n\}$, the objective is to find a tree $T$ whose set of leaves is $[n]$ that maximizes the function $\sum_{i Copy to Clipboard Download APA Alon, N., Azar, Y. & Vainstein, D.. (2020). Hierarchical Clustering: A 0.585 Revenue Approximation. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:153-162 Available from https://proceedings.mlr.press/v125/alon20b.html. Copy to Clipboard Download Related Material Download PDF This site last compiled Sun, 05 Jul 2026 14:50:23 +0000 Github Account Copyright © The authors and PMLR 2026. MLResearchPress

Let H be a class of boolean functions and consider a composed class H’ that is derived from H using some arbitrary aggregation rule (for example, H’ may be the class of all 3-wise majority-votes of functions in H). We upper bound the Littlestone dimension of H’ in terms of that of H. As a corollary, we derive closure properties for online learning and private PAC learning. The derived bounds on the Littlestone dimension exhibit an undesirable exponential dependence. For private learning, we prove close to optimal bounds that circumvents this suboptimal dependency. The improved bounds on the sample complexity of private learning are derived algorithmically via transforming a private learner for the original class H to a private learner for the composed class H’. Using the same ideas we show that any (proper or improper) private algorithm that learns a class of functions H in the realizable case (i.e., when the examples are labeled by some function in the class) can be transformed to a private algorithm that learns the class H in the agnostic case.

We study a natural generalization of the classical $ε$-net problem (Haussler--Welzl 1987), which we call the "$ε$-$t$-net problem": Given a hypergraph on $n$ vertices and parameters $t$ and $ε\geq \frac t n$, find a minimum-sized family $S$ of $t$-element subsets of vertices such that each hyperedge of size at least $εn$ contains a set in $S$. When $t=1$, this corresponds to the $ε$-net problem. We prove that any sufficiently large hypergraph with VC-dimension $d$ admits an $ε$-$t$-net of size $O(\frac{ (1+\log t)d}ε \log \frac{1}ε)$. For some families of geometrically-defined hypergraphs (such as the dual hypergraph of regions with linear union complexity), we prove the existence of $O(\frac{1}ε)$-sized $ε$-$t$-nets. We also present an explicit construction of $ε$-$t$-nets (including $ε$-nets) for hypergraphs with bounded VC-dimension. In comparison to previous constructions for the special case of $ε$-nets (i.e., for $t=1$), it does not rely on advanced derandomization techniques. To this end we introduce a variant of the notion of VC-dimension which is of independent interest.

We consider the problem of determining the maximal $\alpha \in (0,1]$ such that every matching $M$ of size $k$ (or at most $k$) in a bipartite graph $G$ contains an induced matching of size at least $\alpha |M|$. This measure was recently introduced in [N. Alon et al., Adv. Neural Inf. Process. Syst., 2017, pp. 2097--2106] and is motivated by computational models in cognitive neuroscience as well as by modeling interference in radio and communication networks. We prove various hardness results for computing $\alpha$ either exactly or approximately. En route to our results, we also consider the maximum connected matching problem: determining the largest matching $N$ in a graph $G$ such that every two edges in $N$ are connected by an edge. We prove a nearly optimal $n^{1-\epsilon}$ hardness of approximation result (under randomized reductions) for connected matching in bipartite graphs (with both sides of cardinality $n$). Toward this end we define bipartite half-covers: a new combinatorial object that may be of independent interest. To our knowledge, the best previous hardness result for the maximum connected matching problem was that it is hard to approximate within some constant $\beta>1$. Finally, we demonstrate the existence of bipartite graphs with $n$ vertices on each side of average degree $d$, achieving $\alpha=1/2-\epsilon$ for matchings of size sufficiently smaller than $n/d$. This nearly matches the trivial upper bound of $1/2$ on $\alpha$ which holds for any graph containing a path of length 3.

In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O~(m sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same O~(m sqrt{n}) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of O~(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in O~(m sqrt{n}) time, and a deterministic algorithm for the k-simple shortest paths problem in O~(k m sqrt{n}) time (for any integer constant k > 0). For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t in V and F subseteq E cup V, |F| <=f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with O~(mn^{4-alpha}) preprocessing time and subquadratic O~(n^{2-2(1-alpha)/f}) query time, giving a tradeoff between preprocessing and query time for every value of 0 < alpha < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time.

We consider learning problems where the training set consists of two types of examples: private and public. The goal is to design a learning algorithm that satisfies differential privacy only with respect to the private examples. This setting interpolates between private learning (where all examples are private) and classical learning (where all examples are public). We study the limits of learning in this setting in terms of private and public sample complexities. We show that any hypothesis class of VC-dimension $d$ can be agnostically learned up to an excess error of $\alpha$ using only (roughly) $d/\alpha$ public examples and $d/\alpha^2$ private labeled examples. This result holds even when the public examples are unlabeled. This gives a quadratic improvement over the standard $d/\alpha^2$ upper bound on the public sample complexity (where private examples can be ignored altogether if the public examples are labeled). Furthermore, we give a nearly matching lower bound, which we prove via a generic reduction from this setting to the one of private learning without public data.

We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension d requires Ω(log*(d)) examples. As a corollary it follows that the class of thresholds over ℕ can not be learned in a private manner; this resolves open questions due to [Bun et al. 2015] and [Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.

We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n -party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding scheme that takes \(R'\) rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotic rate , i.e., while keeping \(\liminf _{n,R\rightarrow \infty } R/R'\) positive. Rajagopalan and Schulman (STOC ’94) were the first to consider this question, and provided a coding scheme with rate \(O(1/\log (d+1))\) , where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is \(O(1/\log n)\) , which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a ( d -regular) network has mixing time m , then there exists an efficient coding scheme with rate \(O(1/m^3\log m)\) . This implies a constant rate coding scheme for any n -party protocol over a d -regular network with a constant mixing time, and in particular for random graphs with n vertices and degrees \(n^{\varOmega (1)}\) .

We prove that the minimum number of vertices of a hypergraph that contains every $d$-uniform hypergraph on $k$ vertices as an induced subhypergraph is $(1+o(1))2^{\binom{k}{d}/k}$. The proof relies on the probabilistic method and provides a nonconstructive solution. In addition we exhibit an explicit construction of a hypergraph on $\Theta(2^{\binom{k}{d}/k})$ vertices, containing every $d$-uniform hypergraph on $k$ vertices as an induced subhypergraph.

We consider list decoding in the zero-rate regime for two cases-the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal τ ∈ [0, 1] for which there exists an arrangement of M balls of relative Hamming radius τ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by L or more of them. As M → ∞ the maximal τ decreases to a well-known critical value τL. In this paper, we prove several results on the rate of this convergence. For the binary case, we show that the rate is Θ(M-1) when L is even, thus extending the classical results of Plotkin and Levenshtein for L = 2. For L = 3, the rate is shown to be Θ(M-(2/3)). For the similar question about spherical codes, we prove the rate is Ω(M-1) and O(M-(2L/L(2)-L+2)).

In this paper we provide a tight bound for the price of preemption for scheduling jobs on a single machine (or multiple machines). The input consists of a set of jobs to be scheduled and of an integer parameter $k \ge 1$. Each job has a release time, deadline, length (also called processing time) and value associated with it. The goal is to feasibly schedule a subset of the jobs so that their total value is maximal; while preemption of a job is permitted, a job may be preempted no more than k times. The price of preemption is the worst possible (i.e., largest) ratio of the optimal non-bounded-preemptive scheduling to the optimal k-bounded-preemptive scheduling. Our results show that allowing at most k preemptions suffices to guarantee a Θ(\min\łog_k+1 n, łog_k+1 P\ )$ fraction of the total value achieved when the number of preemptions is unrestricted (where n is the number of the jobs and P the ratio of the maximal length to the minimal length), giving us an upper bound for the price; a specific scenario serves to prove the tightness of this bound. We further show that when no preemptions are permitted at all (i.e., k=0), the price is Θ(\min\n, łog P\ )$. As part of the proof, we introduce the notion of the Bounded-Degree Ancestor-Free Sub-Forest (BAS). We investigate the problem of computing the maximal-value BAS of a given forest and give a tight bound for the loss factor, which is Θ(łog_k+1 n)$ as well, where n is the size of the original forest and k is the bound on the degree of the sub-forest.

We consider properties of edge-colored vertex-ordered graphs - graphs with a totally ordered vertex set and a finite set of possible edge colors - showing that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of two-dimensional matrices over a finite alphabet (where row and column order is not ignored) is strongly testable. The first result generalizes the result of Alon and Shapira [FOCS'05; SICOMP'08], who showed that any hereditary graph property (without vertex order) is strongly testable. The second result answers and generalizes a conjecture of Alon, Fischer and Newman [SICOMP'07] concerning testing of matrix properties. The testability is proved by establishing a removal lemma for vertex-ordered graphs. It states that if such a graph is far enough from satisfying a certain hereditary property, then most of its induced vertex-ordered subgraphs on a certain (large enough) constant number of vertices do not satisfy the property as well. The proof bridges the gap between techniques related to the regularity lemma, used in the long chain of papers investigating graph testing, and string testing techniques. Along the way we develop a Ramsey-type lemma for multipartite graphs with “undesirable” edges, stating that one can find a Ramsey-type structure in such a graph, in which the density of the undesirable edges is not much higher than the density of those edges in the graph.

Let X be a set of n points of norm at most 1 in the Euclidean space R^k, and suppose ≥0. An ≥-distance sketch for X is a data structure that, given any two points of X enables one to recover the square of the (Euclidean) distance between them up to an additive} error of ≥. Let f(n,k,≥) denote the minimum possible number of bits of such a sketch. Here we determine f(n,k,≥) up to a constant factor for all n ≥ k ≥ 1 and all ≥ ≥ \frac{1}{n^{0.49}}. Our proof is algorithmic, and provides an efficient algorithm for computing a sketch of size O(f(n,k,≥)/n) for each point, so that the square of the distance between any two points can be computed from their sketches up to an additive error of ≥ in time linear in the length of the sketches. We also discuss the case of smaller ≥2/√ n and obtain some new results about dimension reduction in this range. In particular, we show that for any such ≥ and any k ≤ t=\frac{\log (2+≥^2 n)}{≥^2} there are configurations of n points in R^k that cannot be embedded in R^{ℓ} for ℓ

A key feature of neural network architectures is their ability to support the simultaneous interaction among large numbers of units in the learning and processing of representations. However, how the richness of such interactions trades off against the ability of a network to simultaneously carry out multiple independent processes -- a salient limitation in many domains of human cognition -- remains largely unexplored. In this paper we use a graph-theoretic analysis of network architecture to address this question, where tasks are represented as edges in a bipartite graph $G=(A \cup B, E)$. We define a new measure of multitasking capacity of such networks, based on the assumptions that tasks that \emph{need} to be multitasked rely on independent resources, i.e., form a matching, and that tasks \emph{can} be performed without interference if they form an induced matching. Our main result is an inherent tradeoff between the multitasking capacity and the average degree of the network that holds \emph{regardless of the network architecture}. These results are also extended to networks of depth greater than $2$. On the positive side, we demonstrate that networks that are random-like (e.g., locally sparse) can have desirable multitasking properties. Our results shed light into the parallel-processing limitations of neural systems and provide insights that may be useful for the analysis and design of parallel architectures.

In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the k'th moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.

We show that for any constant Δ ≥ 2, there exists a graph Γ with O(nΔ/2) vertices which contains every n-vertex graph with maximum degree Δ as an induced subgraph. For odd Δ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least Ω(nΔ/2) vertices. Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of Γ is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph H on n vertices with maximum degree at most Δ, an induced subgraph of Γ isomorphic to H.

We introduce and study a partial-information model of online learning, where a decision maker repeatedly chooses from a finite set of actions and observes some subset of the associated losses. This setting naturally models several situations where knowing the loss of one action provides information on the loss of other actions. Moreover, it generalizes and interpolates between the well-studied full-information setting (where all losses are revealed) and the bandit setting (where only the loss of the action chosen by the player is revealed). We provide several algorithms addressing different variants of our setting and provide tight regret bounds depending on combinatorial properties of the information feedback structure.

We consider a broadcast model involving multiple transmitters and receivers. Transmission is performed in rounds, where in each round any transmitter is allowed to broadcast a single message, and each receiver can receive only a single broadcast message, determined by a priority permutation over the transmitters. The message received by receiver $R$ in a given transmission round is the one sent by the first transmitter among all those broadcasting in that round according to the permutation of $R$. In our model, each pair of transmitter and receiver has a unique message which the transmitter has to send to the receiver. We prove upper and lower bounds on the minimal number of rounds needed for transmitting all the messages to their respective receivers. We also consider the case where the priority permutations are determined geometrically.

We study the tandem duplication distance between binary sequences and their roots. In other words, the quantity of interest is the number of tandem duplication operations of the form x = abc → y = abbc, where x and y are sequences and a, b, and c are their substrings, needed to generate a binary sequence of length n starting from a square-free sequence from the set {0, 1, 01, 10, 010, 101}. This problem is a restricted case of finding the duplication/deduplication distance between two sequences, defined as the minimum number of duplication and deduplication operations required to transform one sequence to the other. We consider both exact and approximate tandem duplications. For exact duplication, denoting the maximum distance to the root of a sequence of length n by f(n), we prove that f(n) = Θ(n). For the case of approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show that the maximum distance has a sharp transition from linear in n to logarithmic at β = 1/2. We also study the duplication distance to the root for the set of sequences arising from a given root and for special classes of sequences, namely, the De Bruijn sequences, the Thue-Morse sequence, and the Fibonacci words. The problem is motivated by genomic tandem duplication mutations and the smallest number of tandem duplication events required to generate a given biological sequence.

Let G = (V, E) be a connected undirected graph with k vertices. Suppose that on each vertex of the graph there is a player having an n-bit string. Each player is allowed to communicate with its neighbors according to a (static) agreed communication protocol, and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem ? We determine this minimum up to a lower order additive term in many cases. In particular, we show that it is kn/2 + o(n) for any Hamiltonian k-vertex graph, and that for any 2-edge connected graph with m edges containing no two adjacent vertices of degree exceeding 2 it is mn/2 + o(n). The proofs combine graph theoretic ideas with tools from additive number theory.

This work studies the maximum possible sign rank of N \times N sign matrices with a given VC dimension d. For d=1, this maximum is three. For d=2, this maximum is \tildeΘ(N^1/2). For d >2, similar but slightly less accurate statements hold. Our lower bounds improve over previous ones by Ben-David et al. and can be interpreted as exhibiting a weakness of kernel-based classifiers. Our upper bounds, on the other hand, can be interpreted as exhibiting the universality of kernel-based classifiers. The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve. The upper bound technique is also used to: (i) provide estimates on the number of classes of a given VC dimension, and the number of maximum classes of a given VC dimension – answering a question of Frankl from ’89, and (ii) design an efficient algorithm that provides an O(N/\log(N)) multiplicative approximation for the sign rank (computing the sign rank is equivalent to the existential theory of the reals). We also observe a general connection between sign rank and spectral gaps which is based on Forster’s argument. Consider the N \times N adjacency matrix of a ∆regular graph with a second eigenvalue of absolute value λand ∆≤N/2. We show that the sign rank of the signed version of this matrix is at least ∆/λ. We use this connection to prove the existence of a maximum class C⊆{\pm 1}^N with VC dimension 2 and sign rank \tildeΘ(N^1/2). This answers a question of Ben-David et al. regarding the sign rank of large VC classes. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem. We further describe connections to communication complexity, geometry, learning theory, and combinatorics.

We study the tandem duplication distance between binary sequences and their roots. This distance is motivated by genomic tandem duplication mutations and counts the smallest number of tandem duplication events that are required to take one sequence to another. We consider both exact and approximate tandem duplications, the latter leading to a combined duplication/Hamming distance. The paper focuses on the maximum value of the duplication distance to the root. For exact duplication, denoting the maximum distance to the root of a sequence of length n by f(n), we prove that f(n) = Θ(n). For the case of approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show using the Plotkin bound that the maximum distance has a sharp transition from linear to logarithmic in n at β = 1/2.

Exclusive social groups are ones in which the group members decide whether or not to admit a candidate to the group. Examples of exclusive social groups include academic departments and fraternal organizations. In the present paper we introduce an analytic framework for studying the dynamics of exclusive social groups. In our model, every group member is characterized by his opinion, which is represented as a point on the real line. The group evolves in discrete time steps through a voting process carried out by the group's members. Due to homophily, each member votes for the candidate who is more similar to him (i.e., closer to him on the line). An admission rule is then applied to determine which candidate, if any, is admitted. We consider several natural admission rules including majority and consensus.

A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on n leaves is at most . Using the machinery of flag algebras we improve the currently known bounds regarding this conjecture, in particular we show that the maximum is at most . We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most .

A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on $n$ leaves is at most $(\frac{2}{3}+o(1))\binom{n}{4}$. Using the machinery of flag algebras, we improve the currently known bounds regarding this conjecture; in particular, we show that the maximum is at most $(0.69+o(1))\binom{n}{4}$. We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most $(\frac{2}{3}+o(1))\binom{n}{4}$.

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over GF(2), whose kernel does not intersect a given set S. In the case where S is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set S, this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where S is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius nq and np respectively, the optimal relative rank is given by the normalized entropy (1 - q)H(p/(1 - q)), an extension of the Gilbert-Varshamov bound.

We study a general class of online learning problems where the feedback is specified by a graph. This class includes online prediction with expert advice and the multi-armed bandit problem, but also several learning problems where the online player does not necessarily observe his own loss. We analyze how the structure of the feedback graph controls the inherent difficulty of the induced T-round learning problem. Specifically, we show that any feedback graph belongs to one of three classes: \emphstrongly observable graphs, \emphweakly observable graphs, and \emphunobservable graphs. We prove that the first class induces learning problems with \widetildeΘ(α^1/2 T^1/2) minimax regret, where αis the independence number of the underlying graph; the second class induces problems with \widetildeΘ(δ^1/3T^2/3) minimax regret, where δis the domination number of a certain portion of the graph; and the third class induces problems with linear minimax regret. Our results subsume much of the previous work on learning with feedback graphs and reveal new connections to partial monitoring games. We also show how the regret is affected if the graphs are allowed to vary with time.

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent's valuations are unknown to the central planner, and therefore communication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n1/(r+1)-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size. We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is nε(r), the approximation ratio of any r-round (randomized) protocol is no better than Ω(n1/5r+1), implying an Ω(log log n) lower bound on the rate of convergence of the market to equilibrium. Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

No abstract available.

Entailment rules between predicates are fundamental to many semantic-inference applications. Consequently, learning such rules has been an active field of research in recent years. Methods for learning entailment rules between predicates that take into account dependencies between different rules (e.g., entailment is a transitive relation) have been shown to improve rule quality, but suffer from scalability issues, that is, the number of predicates handled is often quite small. In this article, we present methods for learning transitive graphs that contain tens of thousands of nodes, where nodes represent predicates and edges correspond to entailment rules (termed entailment graphs). Our methods are able to scale to a large number of predicates by exploiting structural properties of entailment graphs such as the fact that they exhibit a “tree-like” property. We apply our methods on two data sets and demonstrate that our methods find high-quality solutions faster than methods proposed in the past, and moreover our methods for the first time scale to large graphs containing 20,000 nodes and more than 100,000 edges.

The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $\mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $\mathcal{F}$ of total orders of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one total order in $\mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $\Theta(\log n)$. In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9{log^{\star}}\!d} d$. We also demonstrate that the above bound is nearly tight by showing that, for every $d$, almost all $d$-regular graphs have separation dimension at least $\ceil{d/2}$.

Given a matrix A, we study how many epsilon-cubes are required to cover the convex hull of the columns of A. We show bounds on this cover number in terms of VC dimension and the gamma_2 norm and give algorithms for enumerating elements of a cover. This leads to algorithms for computing approximate Nash equilibria that unify and extend several previous results in the literature. Moreover, our approximation algorithms can be applied quite generally to a family of quadratic optimization problems that also includes finding the k-by-k combinatorial rectangle of a matrix. In particular, for this problem we give the first quasi-polynomial time additive approximation algorithm that works for any matrix A in [0,1]^{m x n}.

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is formulated as determining the minimal rank of a matrix over GF(2) whose kernel does not intersect a given set S. In the case where S is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set S, this is an instance of “the critical problem” posed by Crapo and Rota in 1970, open in general. This work focuses on the case where S is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius nq and np respectively, the optimal relative rank is given by the normalized entropy (1 - q)H(p=(1 - q)), an extension of the Gilbert-Varshamov bound.

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity. Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. It has been shown that certain wired networks have an asymptotic network coding gap, that is, they have asymptotically higher broadcast throughput when using network coding compared to routing. Whether such a gap exists for wireless networks has been an open question of great interest. We approach this question by studying the broadcast throughput of the radio network model which has been a standard mathematical model to study wireless communication. We show that there is a family of radio networks with a tight Θ(log log n) network coding gap, that is, networks in which the asymptotic throughput achievable via routing messages is a Θ(log log n) factor smaller than that of the optimal network coding algorithm. We also provide new tight upper and lower bounds showing that the asymptotic worst-case broadcast throughput over all networks with n nodes is messages-per-round for both routing and network coding.

Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over n species defines quartets, not every set of quartets is compatible with some phylogenetic tree. Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets Q of size m = cn log n in which every subset of cardinality c′n/logn is compatible, and yet no fraction of more than 1/3+ ∊ of Q is compatible. On the other hand, in contrast to the classical result stating when Q is the densest, i.e. the consistency of any set of 3 quartets implies full consistency, we show that even for there are (very) inconsistent sets for which every subset of large constant cardinality is consistent. Our final result, relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value.

Given a set of $n$ real numbers, if the sum of the elements of every subset of size larger than $k$ is negative, what is the maximum number of subsets of nonnegative sum? In this note we show that the answer is $\binom{n-1}{k-1} + \binom{n-1}{k-2} + \cdots + \binom{n-1}{0}+1$, settling a problem of Tsukerman. We provide two proofs; the first establishes and applies a weighted version of Hall's theorem, and the second is based on an extension of the nonuniform Erdös--Ko--Rado theorem.

We prove a previously stated but incorrectly proved theorem: there is a diameter-3 graph in which replacing any edge $\{v, w\}$ of the graph with $\{v, w'\}$, for any vertex $w'$, does not decrease the total sum of distances from $v$ to all other nodes (a property called sum equilibrium).

Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over $n$ species defines ${n \choose 4}$ quartets, not every set of quartets is compatible with some phylogenetic tree. Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets $Q$ of size $m=c n \log n$ in which every subset of cardinality $c' n/ \log n$ is compatible, and yet no fraction of more than $1/3+\epsilon$ of $Q$ is compatible. On the other hand, in contrast to the classical result stating when $Q$ is the densest, i.e., $m={n \choose 4}$ and the compatibility of any set of three quartets implies full compatibility, we show that even for $m=\Theta\big({n \choose 4}\big)$ there are (very) incompatible sets for which every subset of large constant cardinality is compatible. Our final result relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value.

We consider judgment aggregation over multiple independent issues, where the chairperson has her own opinion, and can try to bias the outcome by bundling several issues together. Since for each bundle judges must give a uniform answer on all issues, different partitions of the issues may result in an outcome that significantly differs from the "true," issue-wise, decision. We prove that the bundling problem faced by the chairperson, i.e. trying to bias the outcome towards her own opinion, is computationally difficult in the worst case. Then we study the probability that an effective bundling attack exists as the disparity between the opinions of the judges and the chair varies. We show that if every judge initially agrees with the chair on every issue with probability of at least 1/2, then there is almost always a bundling attack (i.e. a partition) where the opinion of the chair on all issues is approved. Moreover, such a partition can be found efficiently. In contrast, when the probability is lower than 1/2 then the chair cannot force her opinion using bundling even on a single issue.

We introduce a class of polynomials, which we call U-polynomials and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of U-polynomials, though their size is larger than desired. Furthermore, we give two alternative proofs for the fact that small-bias sets induce rigid matrices. Finally, we construct rigid matrices from unbalanced expanders, with essentially the same size as the construction via small-bias sets.

We consider the partial observability model for multi-armed bandits, introduced by Mannor and Shamir (2011). Our main result is a characterization of regret in the directed observability model in terms of the dominating and independence numbers of the observability graph. We also show that in the undirected case, the learner can achieve optimal regret without even accessing the observability graph before selecting an action. Both results are shown using variants of the Exp3 algorithm operating on the observability graph in a time-efficient manner.

We introduce and study the algorithmic problem of maximizing revenue in a network using differential pricing, where the prices offered to neighboring vertices cannot be substantially different. Our most surprising result is that the optimal pricing can be computed efficiently, even for arbitrary revenue functions. In contrast, we show that if one is allowed to introduce discontinuities (by deleting vertices) the optimization problem becomes computationally hard, and we exhibit algorithms for special classes of graphs. We also study a stochastic model, and show that a similar contrast exists there: For pricing without discontinuities the benefit of differential pricing over a single price is negligible, while for differential pricing with discontinuities the difference is substantial.

We study the ε-rank of a real matrix A, defined for any ε > 0 as the minimum rank over matrices that approximate every entry of A to within an additive ε. This parameter is connected to other notions of approximate rank and is motivated by problems from various topics including communication complexity, combinatorial optimization, game theory, computational geometry and learning theory. Here we give bounds on the ε-rank and use them for algorithmic applications. Our main algorithmic results are (a) polynomial-time additive approximation schemes for Nash equilibria for 2-player games when the payoff matrices are positive semidefinite or have logarithmic rank and (b) an additive PTAS for the densest subgraph problem for similar classes of weighted graphs. We use combinatorial, geometric and spectral techniques; our main new tool is an algorithm for efficiently covering a convex body with translates of another convex body.

We present several variants of the sunflower conjecture of Erdős & Rado (J Lond Math Soc 35:85–90, 1960) and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erdős–Rado sunflower conjecture (if true) implies a negative answer to the “no three disjoint equivoluminous subsets” question of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990); we also formulate a “multicolored” sunflower conjecture in $${\mathbb{Z}_3^n}$$ and show that (if true) it implies a negative answer to the “strong USP” conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith–Winograd conjecture actually implies the Cohn et al. conjecture. The multicolored sunflower conjecture in $${\mathbb{Z}_3^n}$$ is a strengthening of the well-known (ordinary) sunflower conjecture in $${\mathbb{Z}_3^n}$$ , and we show via our connection that a construction from Cohn et al. (2005) yields a lower bound of (2.51 . . .) n on the size of the largest multicolored 3-sunflower-free set, which beats the current best-known lower bound of (2.21 . . . ) n Edel (2004) on the size of the largest 3-sunflower-free set in $${\mathbb{Z}_3^n}$$ .

The generalized nested dissection method, developed by Lipton et al. [1979], is a seminal method for solving a linear systemAx=bwhereAis a symmetric positive definite matrix. The method runs extremely fast wheneverAis a well-separable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work, we extend the nested dissection method to apply toanynonsingular well-separable matrix overanyfield. The running times we obtain essentially match those of the nested dissection method. An important tool is a novel method for matrix sparsification that preserves determinants and minors, and that guarantees that constant powers of the sparsified matrix remain sparse.

We study the problem of testing isomorphism (equivalence up to relabeling of the input variables) between Boolean functions. We prove the following: (1) For most functions $f:\{0,1\}^n \to \{0,1\}$, the query complexity of testing isomorphism to $f$ is $\Omega(n)$. Moreover, the query complexity of testing isomorphism to most $k$-juntas $f:\{0,1\}^n \to \{0,1\}$ is $\Omega(k)$. (2) Isomorphism to any $k$-junta $f:\{0,1\}^n \to \{0,1\}$ can be tested with $O(k \log k)$ queries. (3) For some $k$-juntas $f:\{0,1\}^n \to \{0,1\}$, testing isomorphism to $f$ with one-sided error requires $\Omega(k\log(n/k))$ queries. In particular, testing whether $f:\{0,1\}^n \to \{0,1\}$ is a $k$-parity with one-sided error requires $\Omega(k\log(n/k))$ queries. (4) The query complexity of testing isomorphism between two unknown functions $f,g:\{0,1\}^n \to \{0,1\}$ is $\widetilde{\Theta}(2^{n/2})$. These bounds are tight up to logarithmic factors, and they significantly strengthen the bounds proved by Fischer, Kindler, Ron, Safra, and Samorodnitsky [J. Comput. System Sci., 68 (2004), pp. 753--787] and Blais and O'Donnell [Proceedings of the IEEE Conference on Computational Complexity, 2010, pp. 235--246]. We also obtain results closely related to isomorphism testing, answering a question posed by Diakonikolas, Lee, Matulef, Onak, Rubinfeld, Servedio, and Wan [Proceedings of the IEEE Symposium on Foundations of Computer Science, 2007, pp. 549--558]: testing whether a function $f:\{0,1\}^n \to \{0,1\}$ can be computed by a circuit of size $\le s$ requires $s^{\Omega(1)}$ queries. All of our lower bounds apply to general (adaptive) testers.

When numbers are added in base $b$ in the usual way, carries occur. If two random, independent 1-digit numbers are added, then the probability of a carry is $\frac{b-1}{2b}$. Other choices of digits lead to less carries. In particular, if for odd $b$ we use the digits $\{-(b-1)/2, -(b-3)/2, \ldots , \ldots (b-1)/2\}$ then the probability of carry is only $\frac{b^2-1}{4b^2}$. Diaconis, Shao, and Soundararajan conjectured that this is the best choice of digits, and proved that this is asymptotically the case when $b=p$ is a large prime. In this note we prove this conjecture for all odd primes $p$.

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of $2^{O(\sqrt{\lg n})}$, a lower bound of 3, and a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local-diameter version, we prove a lower bound of $\Omega(\sqrt{n})$ and a tight upper bound of 3 for trees. The same bounds apply, up to constant factors, to the price of anarchy. Our network creation games are closely related to the previously studied unilateral network creation game. The main difference is that our model has no parameter $\alpha$ for the link creation cost, so our results effectively apply for all values of $\alpha$ without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike in previous models. Our perspective enables simpler proofs that get at the heart of network creation games.

While the minimax (or maximin) strategy has become the standard and most agreed-upon solution for decision making in adversarial settings, as discussed in game theory, computer science, and other disciplines, its power arises from the use of mixed strategies, also known as probabilistic algorithms. Nevertheless, in adversarial settings we face the risk of information leakage about the actual strategy instantiation. Hence, real robust algorithms should take information leakage into account. In this paper we introduce the notion of adversarial leakage in games, namely, the ability of a player to learn the value of $b$ binary predicates about the strategy instantiation of her opponent. Different leakage models are suggested and tight bounds on the effect of adversarial leakage as a function of the level of leakage (captured by $b$) are established. The complexity of computing optimal strategies under these adversarial leakage models is also addressed. Together, our study introduces a new framework for robust decision making and provides rigorous fundamental understanding of its properties.

We study sequential voting with two alternatives, in a setting with utility externalities: as usual, each voter has a private preference over the candidates and likes her favorite candidate to win, but additionally, a voter values voting for the chosen winner (which is determined by the majority or super-majority of votes). This model aims to capture voting behavior ("likes") in social networks which are publicly observed and sequential, and in which people care about their "public image" as determined by their votes and the socially accepted outcome (the chosen winner). Unlike in voting with no externalities, voters act strategically although there are only two alternatives, as they rather vote against their preferred candidate if the other is to win. We present two rather surprising results that are derived from the strategic behavior of the voters. First, we show that in sequential voting in which a winner is declared when the gap in votes is at least some large value $M$, increasing $M$ does not result in the aggregation of preferences of more voters in the decision, as voters start a herd on one candidate once a small lead in votes for that candidate develops. Furthermore, the threshold lead for such a herd to start is independent of M. Secondly, we show that there are cases in which sequential voting is strictly better than simultaneous voting, in the sense that it chooses the most preferred alternative with higher probability.

Recently Rubinfeld et al. (ICS 2011, pp. 223–238) proposed a new model of sublinear algorithms called local computation algorithms. In this model, a computation problem F may have more than one legal solution and each of them consists of many bits. The local computation algorithm for F should answer in an online fashion, for any index i, the ith bit of some legal solution of F. Further, all the answers given by the algorithm should be consistent with at least one solution of F. In this work, we continue the study of local computation algorithms. In particular, we develop a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time but also in polylogarithmic space. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. Our main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with (N2)-o(N2) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N1-o(1). The second construction provides a covering of all edges of the complete graph KN by two graphs, each being the edge disjoint union of at most N2-δ induced matchings, where δ>0.076. This disproves (in a strong form) a conjecture of Meshulam, substantially improves a result of Birk, Linial and Meshulam on communicating over a shared channel, and (slightly) extends the analysis of Hastad and Wigderson of the graph test of Samorodnitsky and Trevisan for linearity. Additionally, our constructions settle a combinatorial question of Vempala regarding a candidate rounding scheme for the directed Steiner tree problem.

Brands and agencies use marketing as a tool to influence customers. One of the major decisions in a marketing plan deals with the allocation of a given budget among media channels in order to maximize the impact on a set of potential customers. A similar situation occurs in a social network, where a marketing budget needs to be distributed among a set of potential influencers in a way that provides high-impact.

We consider the special case of approval voting when the set of agents and the set of alternatives coincide. This captures situations in which the members of an organization want to elect a president or a committee from their ranks, as well as a variety of problems in networked environments, for example in internet search, social networks like Twitter, or reputation systems like Epinions. More precisely, we look at a setting where each member of a set of n agents approves or disapproves of any other member of the set and we want to select a subset of k agents, for a given value of k, in a strategyproof and approximately efficient way. Here, strategyproofness means that no agent can improve its own chances of being selected by changing the set of other agents it approves. A mechanism is said to provide an approximation ratio of α for some α ≥ 1 if the ratio between the sum of approval scores of any set of size k and that of the set selected by the mechanism is always at most α. We show that for k ∈ {1, 2,..., n − 1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. We then present a randomized strategyproof mechanism that provides an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.

We consider the problem of partitioning the vertices of an [Formula: see text]-vertex graph with maximum degree [Formula: see text] into [Formula: see text] classes [Formula: see text] of size at most [Formula: see text] in a way that minimizes the number of pairs [Formula: see text] for which there is an edge between [Formula: see text] and [Formula: see text]. We show that there is always such a partition with [Formula: see text] adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems. (A corrected version of this paper has been appended to the originally posted pdf.)

We show that the minimum possible size of an ϵ-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ϵ. This settles a problem raised by Matousek, Seidel and Welzl in 1990.

The generalized nested dissection method, developed by Lipton, Rose, and Tarjan, is a seminal method for solving a linear system Ax=b where A is a symmetric positive definite matrix. The method runs extremely fast whenever A is a well-separable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work we extend the nested dissection method to apply to any non-singular well-separable matrix over any field. The running times we obtain essentially match those of the nested dissection method.

We quantify the effect of Bayesian ignorance by comparing the social cost obtained in a Bayesian game by agents with local views to the expected social cost of agents having global views. Both benevolent agents, whose goal is to minimize the social cost, and selfish agents, aiming at minimizing their own individual costs, are considered. When dealing with selfish agents, we consider both best and worst equilibria outcomes. While our model is general, most of our results concern the setting of network cost sharing (NCS) games. We provide tight asymptotic results on the effect of Bayesian ignorance in directed and undirected NCS games with benevolent and selfish agents. Among our findings we expose the counter-intuitive phenomenon that "gnorance is bliss": Bayesian ignorance may substantially improve the social cost of selfish agents. We also prove that public random bits can replace the knowledge of the common prior in attempt to bound the effect of Bayesian ignorance in settings with benevolent agents. Together, our work initiates the study of the effects of local vs. global views on the social cost of agents in Bayesian contexts.

We present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r – 1)m + k)/2r clauses. Thus Max-r-Sat is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound (1 − 2−r)m. This solves an open problem of Mahajan, Raman and Sikdar (J. Comput. System Sci., 75, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with O(k2) variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size O(k2), then there is a truth assignment satisfying the required number of clauses. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of Max-2-Sat with m clauses has at least 3k variables after application of certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least (3m + k)/4 clauses. We also outline how the fixed-parameter tractability result on Max-r-Sat can be extended to a family of Boolean Constraint Satisfaction Problems.

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes, by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of 2O(√ lg n), a lower bound of 3, a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local-diameter version, we prove a lower bound of Ω(√ n), and a tight upper bound of 3 for trees. All of our upper bounds apply equally well to previously extensively studied network creation games, both in terms of the diameter metric described above and the previously studied price of anarchy (which are related by constant factors). In surprising contrast, our model has no parameter α for the link creation cost, so our results automatically apply for all values of alpha without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike previous models. Our perspective enables simpler and more general proofs that get at the heart of network creation games.

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”

Let $(C_m^d)_{\infty}$ denote the graph whose set of vertices is $Z_m^d$ in which two distinct vertices are adjacent iff in each coordinate either they are equal or they differ, modulo m, by at most 1. Bollobás, Kindler, Leader, and O'Donnell proved that the minimum possible cardinality of a set of vertices of $(C_m^d)_{\infty}$ whose deletion destroys all topologically nontrivial cycles is $m^d-(m-1)^d$. We present a short proof of this result, using the Brunn–Minkowski inequality, and also show that the bound can be achieved only by selecting a value $x_i$ in each coordinate i, $1\leq i\leq d$, and by keeping only the vertices whose ith coordinate is not $x_i$ for all i.

The construction of perfect hash functions is a well-studied topic. In this article, this concept is generalized with the following definition. We say that a family of functions from [ n ] to [ k ] is a δ-balanced ( n,k )-family of perfect hash functions if for every S ⊆ [ n ], | S |= k , the number of functions that are 1-1 on S is between T /δ and δ T for some constant T >0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on S , for each S of size k . In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking δ to be close to 1) for every such S . Our main result is that for any constant δ > 1, a δ-balanced ( n,k )-family of perfect hash functions of size 2 O ( k log log k ) log n can be constructed in time 2 O ( k log log k ) n log n . Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial-time algorithm for approximating both the number of simple paths of length k and the number of simple cycles of size k for any k ≤ O (log n /log log log n ) in a graph with n vertices. The approximation is up to any fixed desirable relative error.

We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

For a binary sequenceSn= {si:i=1,2,...,n} ∈ {±1}n,n> 1, the peak sidelobe level (PSL) is defined as M(Sn)=maxk=1,2,...,n-1|∑i=1n-kSiSi+k|. It is shown that the distribution ofM(Sn) is strongly concentrated, and asymptotically almost surely γ(Sn) = (M(Sn))/√(n In n) ∈ [1-o(1),√2]. Explicit bounds for the number of sequences outside this range are provided. This improves on the best earlier known result due to Moon and Moser that the typical γ(Sn) ∈ [o([1/(√(ln n))]),2], and settles to the affirmative the conjecture of Dmitriev and Jedwab on the growth rate of the typical peak sidelobe. Finally, it is shown that modulo some natural conjecture, the typical γ(Sn) equals√2.

In the classical balls-and-bins paradigm, where n balls are placed independently and uniformly in n bins, typically the number of bins with at least two balls in them is ¿(n) and the maximum number of balls in a bin is ¿((log n)/(log log n)). It is well known that when each round offers k independent uniform options for bins, it is possible to typically achieve a constant maximal load if and only if k = ¿(log n). Moreover, it is possible whp to avoid any collisions between n/2 balls if k > log2n. In this work, we extend this into the setting where only m bits of memory are available. We establish a tradeoff between the number of choices k and the memory m, dictated by the quantity km/n. Roughly put, we show that for km ¿ n one can achieve a constant maximal load, while for km ¿n no substantial improvement can be gained over the case k = 1 (i.e., a random allocation). For any k = ¿(log n) and m = ¿(log2n), one can typically achieve a constant load if km = ¿(n), yet the load is unbounded if km = o(n). Similarly, if km > Cn then n/2 balls can be allocated without any collisions whp, whereas for km1-¿the optimal maximal load is ¿((log n)/(log log n)) (the same as in the case k = 1), while m = 2n suffices to ensure a constant load. Finally, we analyze non-adaptive allocation algorithms and give tight upper and lower bounds for their performance.

An adaptive (n, m, s, t)-scheme is a deterministic scheme for encoding a vector X of m bits with at most n ones by a vector Y of s bits, so that any bit of X can be determined by t adaptive probes to Y. A non-adaptive (n, m, s, t)-scheme is defined analogously. The study of such schemes arises in the investigation of the static membership problem in the bitprobe model. Answering a question of Buhrman, Miltersen, Radhakrishnan and Venkatesh [SICOMP 2002] we present adaptive (n, m, s, 2) schemes with s < m for all n satisfying 4n2 + 4n < m and adaptive (n, m, s, 2) schemes with s = o(m) for all n = o(logm). We further show that there are adaptive (n, m, s, 3)-schemes with s = o(m) for all n = o(m), settling a problem of Radhakrishnan, Raman and Rao [ESA 2001], and prove that there are non-adaptive (n, m, s, 4)-schemes with s = o(m) for all n = o(m). Therefore, three adaptive probes or four non-adaptive probes already suffice to obtain a significant saving in space compared to the total length of the input vector. Lower bounds are discussed as well.

We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is $\mathcal{NP}$ -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in ℘, and for the others it is $\mathcal{NP}$ -complete.

Let $X=\{1,2,\ldots,n\}$ be a ground set of n elements, and let ${\cal S}$ be a family of subsets of X, $|{\cal S}|=m$, with a positive cost $c_S$ associated with each $S\in{\cal S}$. Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one by one. Once a new element is given, the algorithm has to cover it by some set of ${\cal S}$ containing it. We assume that the elements of X and the members of ${\cal S}$ are known in advance to the algorithm; however, the set $X'\subseteq X$ of elements given by the adversary is not known in advance to the algorithm. (In general, $X'$ may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let ${\cal C}$ denote the family of sets in ${\cal S}$ that the algorithm chooses. At the end of the game the adversary also produces (offline) a family of sets ${\cal C}_{OPT}$ that covers $X'$. The performance of the algorithm is the ratio between the cost of ${\cal C}$ and the cost of ${\cal C}_{OPT}$. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm. We present an $O(\log m\log n)$ competitive deterministic algorithm for the problem and establish a nearly matching $\Omega\bigl(\frac{\log n\log m}{\log\log m+\log\log n}\bigr)$ lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting a fractional solution into a deterministic online algorithm.

A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property ${\cal P}$ can be tested with a constant number of queries if and only if testing ${\cal P}$ can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653–750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e., a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that (1) every strongly connected n-vertex digraph D with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; (2) if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph $\mathrm{UG}(D)$ is $O(k\log k)$, and if the digraph is acyclic with a single vertex of in-degree zero, then the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(k\log^2k)}\cdot n^{O(1)}$ whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. On acyclic digraphs the running time of our algorithm is $2^{O(k\log k)}\cdot n^{O(1)}$.

The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so-called regular partition of its vertex set. In this paper we address the following problem: Can a graph have two “distinct” regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand, we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very “similar.” En route, we also give a short argument for deriving a recent variant of the regularity lemma obtained independently by Rödl and Schacht and by Lovász and Szegedy from a previously known variant of the regularity lemma due to Alon et al. in 2000. The proof also provides a deterministic polynomial time algorithm for finding such partitions.

We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the capacity limitations of the network. The admission control problem has been usually analyzed as a benefit problem, where the goal is to devise an online algorithm that accepts the maximum number of requests possible. The problem with this objective function is that even algorithms with optimal competitive ratios may reject almost all of the requests, when it would have been possible to reject only a few. This could be inappropriate for settings in which rejections are intended to be rare events. In this article, we consider preemptive online algorithms whose goal is to minimize the number of rejected requests. Each request arrives together with the path it should be routed on. We show an O (log 2 ( mc ))-competitive randomized algorithm for the weighted case, where m is the number of edges in the graph and c is the maximum edge capacity. For the unweighted case, we give an O (log m log c )-competitive randomized algorithm. This settles an open question of Blum et al. [2001]. We note that allowing preemption and handling requests with given paths are essential for avoiding trivial lower bounds. The admission control problem is a generalization of the online set cover with repetitions problem, whose input is a family of m subsets of a ground set of n elements. Elements of the ground set are given to the online algorithm one by one, possibly requesting each element a multiple number of times. (If each element arrives at most once, this corresponds to the online set cover problem.) The algorithm must cover each element by different subsets, according to the number of times it has been requested. We give an O (log m log n )-competitive randomized algorithm for the online set cover with repetitions problem. This matches a recent lower bound of Ω(log m log n ) given by Korman [2005] (based on Feige [1998]) for the competitive ratio of any randomized polynomial time algorithm, under the BPP ≠ NP assumption. Given any constant ϵ > 0, an O (log m log n )-competitive deterministic bicriteria algorithm is shown that covers each element by at least (1 - ϵ) k sets, where k is the number of times the element is covered by the optimal solution.

Moran, Naor, and Segev have asked what is the minimal r=r(n, k) for which there exists an (n,k)-monotone encoding of length r, i.e., a monotone injective function from subsets of size up to k of {1, 2,..., n} to r bits. Monotone encodings are relevant to the study of tamper-proof data structures and arise also in the design of broadcast schemes in certain communication networks. To answer this question, we develop a relaxation of k-superimposed families, which we call alpha-fraction k -multiuser tracing ((k, alpha)-FUT (fraction user-tracing) families). We show that r(n, k) = Theta(k log(n/k)) by proving tight asymptotic lower and upper bounds on the size of (k, alpha)-FUT families and by constructing an (n,k)-monotone encoding of length O(k log(n/k)). We also present an explicit construction of an (n, 2)-monotone encoding of length 2 log n+O(1), which is optimal up to an additive constant.

We show that the vertices of any plane graph in which every face is of size at least g can be colored by (3g Àý 5)=4 colors so that every color appears in every face. This is nearly tight, as there are plane graphs that admit no vertex coloring of this type with more than (3g+1)=4 colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by 3 colors in which all colors appear in every face is NP-complete even for graphs in which all faces are of size 3 or 4 only. If all faces are of size 3 this can be decided in polynomial time.

We investigate the complexity of the outer face in arrangements of line segments of a fixed length in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected complexity of the outer face, and establish a certain phase transition phenomenon during which the expected complexity of the outer face drops sharply as a function of the total number of segments. In particular we show that up till the phase transition the complexity of the outer face is almost linear in n, and that after the phase transition, the complexity of the outer face is roughly proportional to pn. Our study is motivated by the analysis of a practical point-location algorithm (so-called walk-along-a-line point-location algorithm) and indeed, it explains experimental observations of the behavior of the algorithm on arrangements of random segments.

A sender holds a word x consisting of n blocks xi, each of t bits, and wishes to broadcast a codeword to m receivers, R1,...,Rm. Each receiver Riis interested in one block, and has prior side information consisting of some subset of the other blocks. Let betatbe the minimum number of bits that has to be transmitted when each block is of length t, and let beta be the limit beta=limtrarrinfinbetat/t. Informally, beta is the average communication cost per bit in each block (for long blocks). Finding the coding rate beta, for such an informed broadcast setting, generalizes several coding theoretic parameters related to Informed Source Coding on Demand, Index Coding and Network Coding. In this work we show that usage of large data blocks may strictly improve upon the trivial encoding which treats each bit in the block independently. To this end, we provide general bounds on betat, and prove that for any constant C there is an explicit broadcast setting in which beta = 2 but beta1> C. One of these examples answers a question of . In addition, we provide examples with the following counterintuitive direct-sum phenomena. Consider a union of several mutually independent broadcast settings. The optimal code for the combined setting may yield a significant saving in communication over concatenating optimal encodings for the individual settings. This result also provides new non-linear coding schemes which improve upon the largest known gap between linear and non-linear Network Coding, thus improving the results of. The proofs are based on a relation between this problem and results in the study of Witsenhausen's rate, OR graph products, colorings of Cayley graphs, and the chromatic numbers of Kneser graphs.

We study the k-wise independent relaxation of the usual model G(N,p) of random graphs where, as in this model, N labeled vertices are fixed and each edge is drawn with probability p, however, it is only required that the distribution of any subset of k edges is independent.This relaxation can be relevant in modeling phenomena where only k-wise independence is assumed to hold, and is also useful when the relevant graphs are so huge that handling G(N,p) graphs becomes infeasible, and cheaper random-looking distributions (such as k-wise independent ones) must be used instead. Unfortunately, many well-known properties of random graphs in G(N,p) are global, and it is thus not clear if they are guaranteed to hold in the k-wise independent case. We explore the properties of k-wise independent graphs by providing upper-bounds and lower-bounds on the amount of independence, k, required for maintaining the main properties of G(N,p) graphs: connectivity, Hamiltonicity, the connectivity-number, clique-number and chromatic-number and the appearance of fixed subgraphs. Most of these properties are shown to be captured by either constant k or by some k=poly(log(N)) for a wide range of values of p, implying that random looking graphs on N vertices can be generated by a seed of size poly(log(N)). The proofs combine combinatorial, probabilistic and spectral techniques.

Protein-protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these networks can differ significantly from the others in terms of local structures: e.g. the number of specific network motifs can vary significantly among PPI networks. Counting the number of network motifs provides a major challenge to compare biomolecular networks. Recently developed algorithms have been able to count the number of induced occurrences of subgraphs with k < or = 7 vertices. Yet no practical algorithm exists for counting non-induced occurrences, or counting subgraphs with k > or = 8 vertices. Counting non-induced occurrences of network motifs is not only challenging but also quite desirable as available PPI networks include several false interactions and miss many others. In this article, we show how to apply the 'color coding' technique for counting non-induced occurrences of subgraph topologies in the form of trees and bounded treewidth subgraphs. Our algorithm can count all occurrences of motif G' with k vertices in a network G with n vertices in time polynomial with n, provided k = O(log n). We use our algorithm to obtain 'treelet' distributions for k < or = 10 of available PPI networks of unicellular organisms (Saccharomyces cerevisiae Escherichia coli and Helicobacter Pyloris), which are all quite similar, and a multicellular organism (Caenorhabditis elegans) which is significantly different. Furthermore, the treelet distribution of the unicellular organisms are similar to that obtained by the 'duplication model' but are quite different from that of the 'preferential attachment model'. The treelet distribution is robust w.r.t. sparsification with bait/edge coverage of 70% but differences can be observed when bait/edge coverage drops to 50%.

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

We construct weak ε-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1/r-nets of size O(rα(r)), where α(r) denotes the inverse Ackermann function. For point sets along the moment curve in ℝ d we construct weak 1/r-nets of size r · 2 poly(α(r)) , where the degree of the polynomial in the exponent depends (quadratically) on d. Our constructions result from a reduction to a new problem, which we call stabbing interval chains with j-tuples. Given the range of integers N = [1, n], an interval chain of length k is a sequence of k consecutive, disjoint, nonempty intervals contained in N. A j-tuple $\bar{P}$ = (p1,…,pj) is said to stab an interval chain C = I 1 …I k if each p i falls on a different interval of C. The problem is to construct a small-size family Z of j-tuples that stabs all k-interval chains in N. Let z (j) k (n) denote the minimum size of such a family Z. We derive almost-tight upper and lower bounds for z (j) k (n) for every fixed j; our bounds involve functions α m (n) of the inverse Ackermann hierarchy. Specifically, we show that for j = 3 we have z (3) k (n) = Θ(nα $\lfloor$k/2$\rfloor$ (n)) for all k ≥ 6. For each j≥4, we construct a pair of functions Pʹ j (m), Qʹ j (m), almost equal asymptotically, such that z (j) Pʹ j(m)(n) = O(nα m (n)) and z (j) Qʹ j(m)(n) = Ω(nα m (n)).

The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property testing. Our main result in this paper is a solution of an important special case of this general problem: Call a property tester oblivious if its decisions are independent of the size of the input graph. We show that a graph property ${\cal P}$ has an oblivious one-sided error tester if and only if ${\cal P}$ is semihereditary. We stress that any “natural” property that can be tested (either with one-sided or with two-sided error) can be tested by an oblivious tester. In particular, all the testers studied thus far in the literature were oblivious. Our main result can thus be considered as a precise characterization of the natural graph properties, which are testable with one-sided error. One of the main technical contributions of this paper is in showing that any hereditary graph property can be tested with one-sided error. This general result contains as a special case all the previous results about testing graph properties with one-sided error. More importantly, as a special case of our main result, we infer that some of the most well-studied graph properties, both in graph theory and computer science, are testable with one-sided error. Some of these properties are the well-known graph properties of being perfect, chordal, interval, comparability, permutation, and more. None of these properties was previously known to be testable.

A graph property is called monotone if it is closed under removal of edges and vertices. Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract family of all monotone graph properties was also extensively studied. Our main result in this paper is that any monotone graph property can be tested with one-sided error, and with query complexity depending only on $\epsilon$. This result unifies several previous results in the area of property testing and also implies the testability of well-studied graph properties that were previously not known to be testable. At the heart of the proof is an application of a variant of Szemerédi's regularity lemma. The main ideas behind this application may be useful in characterizing all testable graph properties and in generally studying graph property testing. As a byproduct of our techniques we also obtain additional results in graph theory and property testing, which are of independent interest. One of these results is that the query complexity of testing testable graph properties with one-sided error may be arbitrarily large. Another result, which significantly extends previous results in extremal graph theory, is that for any monotone graph property ${\cal P}$, any graph that is $\epsilon$-far from satisfying ${\cal P}$ contains a subgraph of size depending on $\epsilon$ only, which does not satisfy ${\cal P}$. Finally, we prove the following compactness statement: If a graph G is $\epsilon$-far from satisfying a (possibly infinite) set of monotone graph properties ${\cal P}$, then it is at least $\delta_{{\cal P}}(\epsilon)$-far from satisfying one of the properties.

In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. The algorithm is allowed a small probability of error. This problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when $d = \Theta(n)$, where d is the average degree in the graph and n is the number of vertices. Here we study the complexity of the problem in general graphs, that is, for varying d. In this model a testing algorithm is allowed to ask neighbor queries (i.e., “What is the ith neighbor of vertex v?”), vertex-pair queries (i.e., “Is there an edge between vertices v and u?”), and degree queries (i.e., “What is the degree of vertex v?”). Our main finding is a lower bound of $\Omega(n^{1/3})$ on the necessary number of queries that holds for every $d < n^{1-\nu(n)}$, where $\nu(n) = o(1)$. Since when $d = \Theta(n)$ the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavior of the complexity of testing around n. This lower bound holds for testing H-freeness of every nonbipartite subgraph H. Additionally, we provide sublinear upper bounds for testing triangle-freeness that are at most quadratic in the stated lower bounds, and we describe a transformation from certain one-sided error lower bounds for testing subgraph-freeness to two-sided error lower bounds. Finally, in the course of our analysis we show that dense random Cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the “correct” edge density. The result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.

For a real $c \geq 1$ and an integer n, let $f(n,c)$ denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least $f(n,1)$ vertices. The problem of estimating $f(n,1)$ was posed long ago by Erdős, Fajtlowicz, and Staton. In this paper we obtain the following upper and lower bounds for the asymptotic behavior of $f(n,c)$: (i) For fixed $c>2.1$, $n^{1-O(1/c)} \leq f(n,c) \leq O(cn/\log n)$. (ii) For fixed $c=1+\varepsilon$ with $\varepsilon>0$ sufficiently small, $f(n,c) \geq n^{\Omega(\varepsilon^2/ \ln (1/\varepsilon))}$. (iii) $\Omega (\ln n) \leq f(n,1) \leq O(n^{1/2} \ln^{3/4} n)$. An analogous problem for not necessarily induced subgraphs is briefly considered as well.

A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with $dn$ even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most $n(d+1)/4$ brushes suffice and prove that, for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely $\frac{n}{4}(d+o(d))$, thus solving a problem raised in [M.E. Messinger, R.J. Nowakowski, P. Prałat, and N. Wormald, Cleaning random d-regular graphs with brushes using a degree-greedy algorithm, in Combinatorial and Algorithmic Aspects of Networking, Lecture Notes in Comput. Sci. 4852, Springer, Berlin-Heidelberg, 2007, pp. 13–26].

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding , parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. The (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop several worst-case bounds and approximation algorithms on ordinal embedding. In particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.

We describe a deterministic, polynomial time algorithm for finding edge-disjoint paths connecting given pairs of vertices in an expander. Specifically, the input of the algorithm is a sufficiently strong d-regular expander G on n vertices, and a sequence of pairs si, ti(1lesilesr) of vertices, where, r=Theta(nd log d/log n), and no vertex appears more than d/3 times in the list of all endpoints s1, t1,... ,sr,tr. The algorithm outputs edge-disjoint paths Q1,...,Qr, where Qiconnects siand ti. The paths are constructed online, that is, the algorithm produces Qias soon as it gets si,tiand before the next requests in the sequence are revealed. This improves in several respects a long list of previous algorithms for the above problem, whose study is motivated by the investigation of communication networks. An analogous result is established for vertex disjoint paths in blowups of strong expanders.

We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n1/2). We obtain an Õ(n11/23)-approximation. Our algorithm works with thenatural LP relaxation used in prior work. We use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. This also implies a Õ(n11/23) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.

In this work, we consider the problems of testing whether adistribution over (0,1n) is k-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution.

Alon et. al. [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451–476] showed that every property that is characterized by a finite collection of forbidden induced subgraphs is $\epsilon$-testable. However, the complexity of the test is double-tower with respect to $1/\epsilon$, as the only tool known to construct such tests uses a variant of Szemerédi's regularity lemma. Here we show that any property of bipartite graphs that is characterized by a finite collection of forbidden induced subgraphs is $\epsilon$-testable, with a number of queries that is polynomial in $1/\epsilon$. Our main tool is a new “conditional” version of the regularity lemma for binary matrices, which may be interesting on its own.

We are motivated by the analogue of Turán’s theorem in the hypercube $Q_n$: How many edges can a $Q_d$‐free subgraph of $Q_n$ have? We study this question through its Ramsey‐type variant and obtain asymptotic results. We show that for every odd d it is possible to color the edges of $Q_n$ with $\frac{(d+1)^2}{4}$ colors such that each subcube $Q_d$ is polychromatic, that is, contains an edge of each color. The number of colors is tight up to a constant factor, as it turns out that a similar coloring with ${d+1\choose 2} +1$ colors is not possible. The corresponding question for vertices is also considered. It is not possible to color the vertices of $Q_n$ with $d+2$ colors such that any $Q_d$ is polychromatic, but there is a simple $d+1$ coloring with this property. A relationship to anti‐Ramsey colorings is also discussed. We discover much less about the Turán‐type question which motivated our investigations. Numerous problems and conjectures are raised.

The kth p‐power of a graph G is the graph on the vertex set $V(G)^k$, where two k‐tuples are adjacent iff the number of their coordinates which are adjacent in G is not congruent to 0 modulo p. The clique number of powers of G is polylogarithmic in the number of vertices; thus graphs with small independence numbers in their p‐powers do not contain large homogeneous subsets. We provide algebraic upper bounds for the asymptotic behavior of independence numbers of such powers, settling a conjecture of [N. Alon and E. Lubetzky, Combinatorica, 27 (2007), pp. 13–33] up to a factor of 2. For precise bounds on some graphs, we apply Delsarte’s linear programming bound and Hoffman’s eigenvalue bound. Finally, we show that for any nontrivial graph G, one can point out specific induced subgraphs of large p‐powers of G with neither a large clique nor a large independent set. We prove that the larger the Shannon capacity of $\overline{G}$ is, the larger these subgraphs are, and if G is the complete graph, then some p‐power of G matches the bounds of the Frankl–Wilson Ramsey construction, and is in fact a subgraph of a variant of that construction.

We consider the guessing secrets problem defined by Chung et al. [2001]. This is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of N possible secrets. The player is asked Boolean questions about the secret. For each question, the player picks one of the k secrets adversarially, and answers according to this secret. We present an explicit set of O (log N ) questions together with an efficient (i.e., poly(log N ) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. This answers the main algorithmic question left unanswered by Chung et al. [2001]. The main techniques we use are small ϵ-biased spaces and the notion of list decoding . We also establish bounds on the number of questions needed to solve the k -secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of k secrets.

For integers $n, r geq 2$ and $1 leq k leq r$, a family ${cal F}$ of subsets of $[n] = {1,ldots,n}$ is called $k$ -out-of-$r$ multiple-user tracing if, given the union of any $ell leq r$ sets from the family, one can identify at least $min(k,ell)$ of them. This is a generalization of superimposed families $(k = r)$ and of single-user tracing families $(k = 1)$. The study of such families is motivated by problems in molecular biology and communication. In this correspondence, we study the maximum possible cardinality of such families, denoted by $h(n,r,k)$ , and show that there exist absolute constants $c_1, c_2, c_3, c_4 > 0$ such that $$minleft({c_1over r}, {c_3over k^2}right) leq {log h(n,r,k)over n} leq minleft({c_2over r}, {c_4 log k over k^2}right).$$ In particular, for all $k leq sqrt{r}, ,{log h(n,r,k)over n} =Theta(1/r)$. This improves an estimate of Laczay and Ruszinkó.

We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar "taste" may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player's real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead.

A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was raised in the 1996 paper of Goldreich, Goldwasser and Ron [25] that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

The cut-norm $||A||_C$ of a real matrix $A=(a_{ij})_{i\in R,j\in S}$ is the maximum, over all $I \subset R$, $J \subset S$, of the quantity $|\sum_{i \in I, j\in J} a_{ij}|$. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and we provide an efficient approximation algorithm. This algorithm finds, for a given matrix $A=(a_{ij})_{i\in R,j\in S}$, two subsets $I \subset R$ and $J \subset S$, such that $|\sum_{i \in I, j\in J} a_{ij}| \geq \rho ||A||_C$, where $\rho>0$ is an absolute constant satisfying $\rho >0.56$. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck's inequality. We present three known proofs of Grothendieck's inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [J. ACM, 42 (1995), pp. 1115-1145], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case.

A tournament is an oriented complete graph. The feedback arc set problem for tournaments is the optimization problem of determining the minimum possible number of edges of a given input tournament T whose reversal makes T acyclic. Ailon, Charikar, and Newman showed that this problem is NP-hard under randomized reductions. Here we show that it is in fact NP-hard. This settles a conjecture of Bang-Jensen and Thomassen.

We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to the algorithm in advance. What is not known in advance are the connectivity (bandwidth) or cut demands between vertices in the network which arrive online.We develop a unified framework for designing online algorithms for problems involving connectivity and cuts. We first present a general O (log m )-competitive deterministic algorithm for generating a fractional solution that satisfies the online connectivity or cut demands, where m is the number of edges in the graph. This may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to both directed and undirected graphs. We then show how to obtain integral solutions via an online rounding of the fractional solution. This part of the framework is problem dependent, and applies various tools including results on approximate max-flow min-cut for multicommodity flow, the Hierarchically Separated Trees (HST) method and its extensions, certain rounding techniques for dependent variables, and Räcke's new hierarchical decomposition of graphs.Specifically, our results for the integral case include an O (log m log n )-competitive randomized algorithm for the online nonmetric facility location problem and for a generalization of the problem called the multicast problem. In the nonmetric facility location problem, m is the number of facilities and n is the number of clients. The competitive ratio is nearly tight. We also present an O (log 2 n log k )-competitive randomized algorithm for the online group Steiner problem in trees and an O (log 3 n log k )-competitive randomized algorithm for the problem in general graphs, where n is the number of vertices in the graph and k is the number of groups. Finally, we design a deterministic O (log 3 n log log n )-competitive algorithm for the online multi-cut problem.

This work addresses k-restriction problems , which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σ m that satisfies a given set of k -wise demands. For every k positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. Problems of this form frequently arise in different fields in Computer Science.The standard approach for deterministically solving such problems is via almost k -wise independence or k -wise approximations for other distributions. We offer a generic algorithmic method that yields considerably smaller constructions. To this end, we generalize a previous work of Naor et al. [1995]. Among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct multi-way splitters , using a new discrete version of the topological Necklace Splitting Theorem [Alon 1987].We utilize our methods to show improved constructions for group testing [Ngo and Du 2000] and generalized hashing [Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption P ≠ NP .

The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of independence numbers in strong powers of a fixed graph can exhibit a complex structure, implying that the Shannon capacity of a graph cannot be approximated (up to a subpolynomial factor of the number of vertices) by any arbitrarily large, yet fixed, prefix of the series. This is true even if this prefix shows a significant increase of the independence number at a given power, after which it stabilizes for a while.

The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property-testing. Our main result in this paper is a solution of an important special case of this general problem; Call a property tester oblivious if its decisions are independent of the size of the input graph. We show that a graph property P has an oblivious one-sided error tester, if and only if P is (semi) hereditary. We stress that any "natural" property that can be tested (either with one-sided or with two-sided error) can be tested by an oblivious tester In particular, all the testers studied thus far in the literature were oblivious. Our main result can thus be considered as a precise characterization of the "natural" graph properties, which are testable with one-sided error. One of the main technical contributions of this paper is in showing that any hereditary graph property can be tested with one-sided error. This general result contains as a special case all the previous results about testing graph properties with one-sided error. These include the results of Goldreich et al., [1998] about testing k-colorability, the characterization of Goldreich and Trevisan [2001] of the graph-partition problems that are testable with 1-sided error, the induced vertex colorability properties of Alon et al., [2000], the induced edge colorability properties of Fischer [2001], a transformation from 2-sided to 1-sided error testing [Goldreich and Trevisan, 2001], as well as a recent result about testing monotone graph properties [Alon and Shapira, 2005]. More importantly, as a special case of our main result, we infer that some of the most well studied graph properties, both in graph theory and computer science, are testable with one-sided error. Some of these properties are the well known graph properties of being perfect, chordal, interval, comparability and more. None of these properties was previously known to be testable.

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E/sub P/'(G). The first result of this paper states that the edge-deletion problem can be efficiently approximated for any monotone property. 1) For any /spl epsiv/ > 0 and any monotone property P, there is a deterministic algorithm, which given a graph G of size n, approximates E/sub P/'(G) in time O(n/sup 2/) to within an additive error of /spl epsiv/n/sup 2/. Given the above, a natural question is for which monotone properties one can obtain better additive approximations of E/sub P/'. Our second main result essentially resolves this problem by giving a precise characterization of the monotone graph properties for which such approximations exist; 1. If there is a bipartite graph that does not satisfy P, then there is a /spl delta/ > 0 for which it is possible to approximate E/sub P/' to within an additive error of n/sup 2-/spl delta// in polynomial time. 2) On the other hand, if all bipartite graphs satisfy P, then for any /spl delta/ > 0 it is NP-hard to approximate E/sub P/' to within an additive error of n/sup 2-/spl delta//. While the proof of (1) is simple, the proof of (2) requires several new ideas and involves tools from extremal graph theory together with spectral techniques. This approach may be useful for obtaining other hardness of approximation results. Interestingly, prior to this work it was not even known that computing E/sub P/' precisely for the properties in (2) is NP-hard. We thus answer (in a strong form) a question of Yannakakis [1981], who asked in 1981 if it is possible to find a large and natural family of graph properties for which computing E/sub P/' is NP-hard.

Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random priority depending on its weight. Suppose we want to estimate the sum of an arbitrary subset I ⊆ T. For any q > 2, considering only the q highest priority items from I, we obtain an unbiased estimator of the sum whose relative standard deviation is O(1/√q). Thus to get an expected approximation factor of 1 ± ε, it suffices to consider O(1/±ε2) items from I. Our estimator needs no knowledge of the number of items in the subset I, but we can also estimate that number if we want to estimate averages.The above scheme performs the same role as the on-line aggregation of Hellerstein et al. (SIGMOD'97) but it has the advantage of having expected good performance for any possible sequence of weights. In particular, the performance does not deteriorate in the common case of heavy-tailed weight distributions. This point is illustrated experimentally both with real and synthetic data.We will also show that our approach can be used to improve Cohen's size estimation framework (FOCS'94).

Abstract We study the admission control problem in general networks. Communication requests arrive overtime, and the online algorithm accepts or rejects each request while maintaining the capacity limitations of the network. The admission control problem has been usually analyzed as a benefit problem, where thegoal is to devise an online algorithm that accepts the maximum number of requests possible. The problem with this objective function is that even algorithms with optimal competitive ratios may reject almost allof the requests, when it would have been possible to reject only a few. This could be inappropriate for settings in which rejections are intended to be rare events.In this paper, we consider preemptive online algorithms whose goal is to minimize the number of rejected requests. Each request arrives together with the path it should be routed on. We show an O(log2(mc))-competitive randomized algorithm for the weighted case, where m is the number of edgesin the graph and c is the maximum edge capacity. For the unweighted case, we give an O(log m log c)-competitive randomized algorithm. This settles an open question of Blum, Kalai and Kleinberg raised in [10]. We note that allowing preemption and handling requests with given paths are essential for avoidingtrivial lower bounds. The admission control problem is a generalization of the online set cover with repetitions problem,whose input is a family of m subsets of a ground set of n elements. Elements of the ground set are givento the online algorithm one by one, possibly requesting each element a multiple number of times. (If each element arrives at most once, this corresponds to the online set cover problem.) The algorithm must covereach element by different subsets, according to the number of times it has been requested. We give an O(log m log n)-competitive randomized algorithm for the the online set cover with rep-etitions problem. This matches a recent lower bound of \\Omega (log m log n) given by Feige and Korman forthe competitive ratio of any randomized polynomial time algorithm, under the BP P 6 = N P assumption.Given any constant ffl> 0, we show an O(log m log n)-competitive deterministic bicriteria algorithm thatcovers each element by at least (1-

We introduce a new graph parameter, called the Grothendieck constant of a graph G=(V,E), which is defined as the least constant K such that for every A:E→R,supf:V→S|V|-1 Σ(u,v) ∈ E A(u,v) · ‹f(u),f(v)› ≤ K supf:V→(-1,+1) Σ(u,v)∈ E A(u,v) · f(u)f(v).The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work is motivated by the algorithmic problem of maximizing the quadratic form ∑u,v∈EA(u,v)f(vover all f: V →-1,1, which arises in the study of correlation clustering and in the investigation of the spin glass model. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is O(log θḠ)) where θ(Ḡ) is the Lovasz Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also show that the maximum possible integrality gap is always at least Ω(log ω(G)), where Ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n Θ vertices with no loops is ⏷(log n ). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is ⏷(log n). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.

A graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs (or, equivalently, if it is closed under removal of edges and vertices). Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract family of all monotone graph properties was also extensively studied. Our main result in this paper is that any monotone graph property can be tested with one-sided error, and with query complexity depending only on ε. This result unifies several previous results in the area of property testing, and also implies the testability of well-studied graph properties that were previously not known to be testable. At the heart of the proof is an application of a variant of Szemerédi's Regularity Lemma. The main ideas behind this application may be useful in characterizing all testable graph properties, and in generally studying graph property testing.As a byproduct of our techniques we also obtain additional results in graph theory and property testing, which are of independent interest. One of these results is that the query complexity of testing testable graph properties with one-sided error may be arbitrarily large. Another result, which significantly extends previous results in extremal graph-theory, is that for any monotone graph property P, any graph that is ε -far from satisfying P, contains a subgraph of size depending on ε only, which does not satisfy P. Finally, we prove the following compactness statement: If a graph G is ε-far from satisfying a (possibly infinite) set of graph properties P, then it is at least δ P ε-far from satisfying one of the properties.

We consider the problem of learning a labeled graph from a given family of graphs on n vertices in a model where the only allowed operation is to query whether a set of vertices induces an edge. Questions of this type are motivated by problems in molecular biology. In the deterministic nonadaptive setting, we prove nearly matching upper and lower bounds for the minimum possible number of queries required when the family is the family of all stars of a given size or all cliques of a given size. We further describe some bounds that apply to general graphs.

A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits. We show that the Reed-Muller codes of constant order are locally testable. Specifically, we describe an efficient randomized algorithm to test if a given vector of length n=2/sup m/ is a word in the rth-order Reed-Muller code R(r,m) of length n=2/sup m/. For a given integer r/spl ges/1, and real /spl epsi/>0, the algorithm queries the input vector /spl upsi/ at O(1//spl epsi/+r2/sup 2r/) positions. On the one hand, if /spl upsi/ is at distance at least /spl epsi/n from the closest codeword, then the algorithm discovers it with probability at least 2/3. On the other hand, if /spl upsi/ is a codeword, then it always passes the test. Our result is almost tight: any algorithm for testing R(r,m) must perform /spl Omega/(1//spl epsi/+2/sup r/) queries.

We prove generalization error bounds for predicting entries in a partially observed matrix by fitting the observed entries with a low-rank matrix. In justifying the analysis approach we take to obtain the bounds, we present an example of a class of functions of finite pseudodimension such that the sums of functions from this class have unbounded pseudodimension. 1 Introduction "Collaborative filtering" refers to the general task of providing users with information on what items they might like, or dislike, based on their preferences so far and how they relate to the preferences of other users. This approach contrasts with a more traditional feature- based approach where predictions are made based on features of the items. For feature-based approaches, we are accustomed to studying prediction methods in terms of probabilistic post-hoc generalization error bounds. Such results provide us a (proba- bilistic) bound on the performance of our predictor on future examples, in terms of its performance on the training data. These bounds hold without any assumptions on the true "model", that is the true dependence of the labels on the features, other than the central assumptions that the training examples are drawn i.i.d. from the distribution of interest. In this paper we suggest studying the generalization ability of collaborative prediction methods. By "collaborative prediction" we indicate that the objective is to be able to pre- dict user preferences for items, that is, entries in some unknown target matrix Y of user- item "ratings", based on observing a subset YS of the entries in this matrix1. We present 1In other collaborative filtering tasks, the objective is to be able to provide each user with a few items that overlap his top-rated items, while it is not important to be able to correctly predict the users ratings for other items. Note that it is possible to derive generalization error bounds for this objective based on bounds for the "prediction" objective. arbitrary source distribution target matrix Y random training set random set S of observed entries hypothesis predicted matrix X training error observed discrepancy DS(X; Y ) generalization error true discrepancy D(X; Y ) Figure 1: Correspondence with post-hoc bounds on the generalization error for standard feature-based prediction tasks bounds on the true average overall error D(X; Y ) = 1 n m loss(X nm i=1 a=1 ia; Yia) of the predictions X in terms of the average error over the observed entries DS(X; Y ) = 1 loss(X |S| iaS ia; Yia), without making any assumptions on the true nature of the pref- erences Y . What we do assume is that the subset S of entries that we observe is chosen uniformly at random. This strong assumption parallels the i.i.d. source assumption for feature-based prediction. In particular, we present generalization error bounds on prediction using low-rank models. Collaborative prediction using low-rank models is fairly straight forward. A low-rank ma- trix X is sought that minimizes the average observed error DS(X; Y ). Unobserved entries in Y are then predicted according to X. The premise behind such a model is that there are only a small number of factors influencing the preferences, and that a user's preference vector is determined by how each factor applies to that user. Different methods differ in how they relate real-valued entries in X to preferences in Y , and in the associated measure of discrepancy. For example, entries in X can be seen as parameters for a probabilistic models of the entries in Y , either mean parameters [1] or natural parameters [2], and a maximum likelihood criterion used. Or, other loss functions, such as squared error [3, 2], or zero-one loss versus the signs of entries in X, can be minimized. Prior Work Previous results bounding the error of collaborative prediction using a low- rank matrix all assume the true target matrix Y is well-approximated by a low-rank matrix. This corresponds to a large eigengap between the top few singular values of Y and the remaining singular values. Azar et al [3] give asymptotic results on the convergence of the predictions to the true preferences, assuming they have an eigengap. Drineas et al [4] analyze the sample complexity needed to be able to predict a matrix with an eigengap, and suggests strategies for actively querying entries in the target matrix. To our knowledge, this is the first analysis of the generalization error of low-rank methods that do not make any assumptions on the true target matrix. Generalization error bounds (and related online learning bounds) were previously discussed for collaborative prediction applications, but only when prediction was done for each user separately, using a feature-based method, with the other user's preferences as features [5, 6]. Although these address a collaborative prediction application, the learning setting is a standard feature-based setting. These methods are also limited, in that learning must be performed separately for each user. Shaw-Taylor et al [7] discuss assumption-free post-hoc bounds on the residual errors of low-rank approximation. These results apply to a different setting, where a subset of the rows are fully observed, and bound a different quantity--the distance between rows and the learned subspace, rather then the distance to predicted entries. Organization In Section 2 we present a generalization error bound for zero-one loss, based on a combinatorial result which we prove in Section 3. In Section 4 we generalize the bound to arbitrary loss functions. Finally, in Section 5 we justify the combinatorial approach taken, by considering an alternate approach (viewing rank-k matrices as combi- nation of k rank-1 matrices) and showing why it does not work. 2 Generalization Error Bound for Zero-One Error We begin by considering binary labels Yia and a zero-one sign agreement loss: loss(Xia; Yia) = 1YiaXia0 (1) Theorem 1. For any matrix Y {1}nm, n, m > 2, > 0 and integer k, with proba- bility at least 1 - over choosing a subset S of entries in Y uniformly among all subsets of |S| entries, the discrepancy with respect to the zero-one sign agreement loss satisfies2: k(n + m) log 16em - log k X,rank X<k D(X ; Y ) < D (X ; Y ) + S 2|S| To prove the theorem we employ standard arguments about the generalization error for finite hypothesis classes with bounded cardinality. First fix Y as well as X nm R . When an index pair (i, a) is chosen uniformly at random, loss(Xia; Yia) is a Bernoulli random variable with probability D(X; Y ) of being one. If the entries of S are chosen independently and uniformly, |S|D(X; Y ) is Binomially S distributed with mean |S|D(X; Y ) and using Chernoff's inequality: Pr D(X; Y ) D(X; Y ) + e-2|S| 2 (2) S S The distribution of S in Theorem 1 is slightly different, as S is chosen without repetitions. The mean of D(X; Y ) is the same, but it is more concentrated, and (2) still holds. S Now consider all rank-k matrices. Noting that loss(Xia; Yia) depends only on the sign of Xia, it is enough to consider the equivalence classes of matrices with the same sign patterns. Let f (n, m, k) be the number of such equivalence classes, i.e. the number of possible sign configurations of n m matrices of rank at most k: F (n, m, k) = {sign X {-, 0, +}nm|X nm R , rank X k} f (n, m, k) = F (n, m, k) 1 If Xia > 0 where sign X denotes the element-wise sign matrix (sign X)ia = 0 If Xia = 0 . -1 If Xia < 1 For all matrices in an equivalence class, the random variable D(X; Y ) is the same, and S taking a union bound of the events D(X; Y ) D(X; Y )+ for each of these f (n, m, k) S random variables we have: log f (n, m, k) - log Pr X,rank XkD(X; Y ) D(X; Y ) + (3) S S 2|S| by using (2) and setting = log f (n,m,k)-log . The proof of Theorem 1 rests on bounding 2|S| f (n, m, k), which we will do in the next section. Note that since the equivalence classes we defined do not depend on the sample set, no symmetrization argument is necessary. 2All logarithms are base two 3 Sign Configurations of a Low-Rank Matrix In this section, we bound the number f (n, m, k) of sign configurations of n m rank- k matrices over the reals. Such a bound was previously considered in the context of unbounded error communication complexity. Alon, Frankl and Rodl [8] showed that f (n, m, k) minh (8 nm/h )(n+m)k+h+m, and used counting arguments to establish that some (in fact, most) binary matrices can only be realized by high-rank matrices, and therefore correspond to functions with high unbounded error communication complexity. Here, we follow a general course outlined by Alon [9] to obtain a simpler, and slightly tighter, bound based on the following result due to Warren: Let P1, . . . , Pr be real polynomials in q variables, and let C be the complement of the variety defined by iPi, i.e. the set of points in which all the m polynomials are non-zero: C = {x q R |iPi(x) = 0} Theorem 2 (Warren [10]). If all r polynomials are of degree at most d, then the number of connected components of C is at most: q q r 4edr c(C) 2(2d)q 2i i q i=0 where the second inequality holds when r > q > 2. The signs of the polynomials P1, . . . , Pr are fixed inside each connected component of C. And so, c(C) bounds the number of sign configurations of P1, . . . , Pr that do not contain zeros. To bound the overall number of sign configurations the polynomials are modified slightly (see Appendix), yielding: Corollary 3 ([9, Proposition 5.5]). The number of -/0/+ sign configurations of r polyno- mials, each of degree at most d, over q variables, is at most (8edr/q)q (for r > q > 2). In order to apply these bounds to low-rank matrices, recall that any matrix X of rank at most k can be written as a product X = U V where U nk km R and V R . Consider the k(n+m) entries of U, V as variables, and the nm entries of X as polynomials of degree two over these variables: k Xia = UiVa =1 Applying Corollary 3 we obtain: k(n+m) Lemma 4. f (n, m, k) 8e2nm (16em/k)k(n+m) k(n+m) Substituting this bound in (3) establishes Theorem 1. The upper bound on f (n, m, k) is tight up to a multiplicative factor in the exponent: 1 Lemma 5. For m > k2, f (n, m, k) m (k-1)n 2 Proof. Fix any matrix V mk R with rows in general position, and consider the number f (n, V, k) of sign configurations of matrices U V , where U varies over all n k matrices. Focusing only on +/- sign configurations (no zeros in U V ), each row of sign U V is a homogeneous linear classification of the rows of V , i.e. of m vectors in general position in k m R . There are exactly 2 k-1 possible homogeneous linear classifications of m i=0 i vectors in general position in k R , and so these many options for each row of sign U V . We can therefore bound: n k-1 n n(k-1) 1 f (n, m, k) f (n, V, k) 2 m m m = m (k-1)n 2 i k-1 k-1 i=0 4 Generalization Error Bounds for Other Loss Functions In Section 2 we considered generalization error bounds for a zero-one loss function. More commonly, though, other loss functions are used, and it is desirable to obtain generalization error bounds for general loss functions. When dealing with other loss functions, the magnitude of the entries in the matrix are important, and not only their signs. It is therefore no longer enough to bound the number of sign configurations. Instead, we will bound not only the number of ways low rank matrices behave with regards to a threshold of zero, but the number of possible ways low- rank matrices can behave relative to any set of thresholds. That is, for any threshold matrix T nm R , we will show that the number of possible sign configurations of (X - T ), where X is low-rank, is small. Intuitively, this captures the complexity of the class of low-rank matrices not only around zero, but throughout all possible values. We then use standard results from statistical machine learning to obtain generalization error bounds from the bound on the number of relative sign configurations. The number of rela- tive sign configurations serves as a bound on the pseudodimension--the maximum number of entries for which there exists a set of thresholds such that all relative sign configurations (limited to these entries) is possible. The pseudodimension can in turn be used to show the existence of a small -net, which is used to obtain generalization error bounds. Recall the definition of the pseudodimension of a class of real-valued functions: Definition 1. A class F of real-valued functions pseudo-shatters the points x1, . . . , xn with thresholds t1, . . . , tn if for every binary labeling of the points (s1, . . . , sn) {+, -}n there exists f F s.t. f (xi) ti iff si = -. The pseudodimension of a class F is the supremum over n for which there exist n points and thresholds that can be shattered. In order to apply known results linking the pseudodimension to covering numbers, we consider matrices X nm R as real-valued functions X : [n] [m] R over index pairs to entries in the matrix. The class Xk of rank-k matrices can now be seen as a class of real-valued functions over the domain [n] [m]. We bound the pseudodimension of this class by bounding, for any threshold matrix T nm R the number of relative sign matrices: F nm T (n, m, k) = {sign (X - T ) {-, 0, +}nm|X R , rank X k} fT (n, m, k) = FT (n, m, k) k(n+m) Lemma 6. For any T nm R , we have fT (n, m, k) 16em . k Proof. We take a similar approach to that of Lemma 4, writing rank-k matrices as a product X = U V where U nk km R and V R . Consider the k(n + m) entries of U, V as variables, and the nm entries of X - T as polynomials of degree two over these variables: k (X - T )ia = UiVa - Tia =1 Applying Corollary 10 yields the desired bound. Corollary 7. The pseudodimension of the class Xk of n m matrices over the reals of rank at most k, is at most k(n + m) log 16em . k We can now invoke standard generalization error bounds in terms of the pseudodimension (Theorem 11 in the Appendix) to obtain: Theorem 8. For any monotone loss function with |loss| M , any matrix Y {1}nm, n, m > 2, > 0 and integer k, with probability at least 1 - over choosing a subset S of entries in Y uniformly among all subsets of |S| entries: k(n + m) log 16em log M|S| - log k k(n+m) X,rank X<k D(X ; Y ) < DS (X ; Y ) + 6 |S| 5 Low-Rank Matrices as Combined Classifiers Rank-k matrices are those matrices which are a sum of k rank-1 matrices. If we view matrices as functions from pairs of indices to the reals, we can think of rank-k matrices as "combined" classifiers, and attempt to bound their complexity as such, based on the low complexity of the "basis" functions, i.e. rank-1 matrices. A similar approach is taken in related work on learning with low-norm (maximum margin) matrix factorization [11, 12], where the hypothesis class can be viewed as a convex combi- nation of rank-1 unit-norm matrices. Scale-sensitive (i.e. dependent on the margin, or the slope of the loss function) generalization error bounds for this class are developed based on the graceful behavior of scale-sensitive complexity measures (e.g. log covering numbers and the Rademacher complexity) with respect to convex combinations. Taking a similar view, it is possible to obtain scale-sensitive generalization error bounds for low-rank ma- trices. In this Section we question whether it is possible to obtain scale-insensitive bounds, similar to Theorems 1 and 8, by viewing low-rank matrices as combined classifiers. It cannot be expected that scale-insensitive complexity would be preserved when taking convex combinations of an unbounded number of base functions. However, the VC- dimension, a scale-insensitive measure of complexity, does scale gracefully when taking linear combinations of a bounded number of functions from a low VC-dimension class of indicator function. Using this, we can obtain generalization error bounds for linear com- binations of signs of rank-one matrices, but not signs of linear combinations of rank-one matrices. An alternate candidate scale-insensitive complexity measure is the pseudodi- mension of a class of real-valued functions. If we could bound the pseudodimension of the class of sums of k functions from a bounded-pseudodimension base class of real valued functions, we could avoid the sign-configuration counting and obtain generalization error bounds for rank-k matrices. Unfortunately, the following counterexample shows that this is not possible. Theorem 9. There exists a family F closed under scalar multiplication whose pseudodi- mension is at most five, and such that {f1 + f2|f1, f2 F } does not have a finite pseu- dodimension. Proof. We describe a class F of real-valued functions over the positive integers N. To do so, consider a one-to-one mapping of finite sets of positive integers to the positive integers. For each A N define two functions3, fA(x) = 2xA + 1xA and gA(x) = 2xA. Let F be the set of all scalar multiplications of these functions. For every A N , fA - gA is the indicator function of A, implying that every finite subset can be shattered, and the pseudodimension of {f1 + f2 : f1, f2 F } is unbounded. It remains to show that the pseudodimension of F is less than six. To do so, we note that there are no positive integers A < B and x < y and positive reals , > 0 such that (2xB + 1) > 2xA and 2yB < (2yA + 1). It follows that for any A < B and any , > 0, on an initial segment (possibly empty) of N we have gB fB gA fA while on the rest of N we have gA fA < gB fB. In particular, any pair of 3We use A to refer both to a positive integer and the finite set it maps to. functions (fA, fB) or (fA, gB) or (gA, gB) in F that are not associated with the same subset (i.e. A = B), cross each other at most once. This holds also when or are negative, as the functions never change signs. For any six naturals x1 < x2 < < x6 and six thresholds, consider the three labellings (+, -, +, -, +, -), (-, +, -, +, -, +), (+, +, -, -, +, +). The three functions realizing these labellings must cross each other at least twice, but by the above arguments, there are no three functions in F such that every pair crosses each other at least twice.4 6 Discussion Alon, Frankl and Rodl [8] use a result of Milnor similar to Warren's Theorem 2. Milnor's and Warren's theorems were previously used for bounding the VC-dimension of certain geometric classes [13], and of general concept classes parametrized by real numbers, in terms of the complexity of the boolean formulas over polynomials used to represent them [14]. This last general result can be used to bound the VC-dimension of signs of nm rank- k matrices by 2k(n + m) log(48enm), yielding a bound similar to Theorem 1 with an extra log |S| term. In this paper, we take a simpler path, applying Warren's theorem directly, and thus avoiding the log |S| term and reducing the other logarithmic term. Applying Warren's theorem directly also enables us to bound the pseudodimension and obtain the bound of Theorem 8 for general loss functions. Another notable application of Milnor's result, which likely inspired these later uses, is for bounding the number of configurations of n points in d R with different possible linear clas- sifications [15, 16]. Viewing signs of rank-k n m matrices as n linear classification of m points in k R , this bound can be used to bound f (n, m, k) < 2km log 2n+k(k+1)n log n with- out using Warren's Theorem directly [8, 12]. The bound of Lemma 4 avoids the quadratic dependence on k in the exponent. Acknowledgments We would like to thank Peter Bartlett for pointing out [13, 14]. N.S. and T.J. would like to thank Erik Demaine for introducing them to oriented matroids. A Proof of Corollary 3 Consider a set R q R containing one variable configuration for each possible sign pattern. Set . = 1 min (x) = P 2 1iq,xRPi(x)=0 |Pi(x)| > 0. Now consider the 2q polynomials P + i i(x) + and P -(x) = P q | (x) = 0, P -(x) = 0 . Different points in R i i(x) - and C = x R iP + i i (representing all sign configurations) lie in different connected components of C . Invoking Theorem 2 on C establishes Corollary 3. The count in Corollary 3 differentiates between positive, negative and zero signs. However, we are only concerned with the positivity of YiaXia (in the proof of Theorem 1) or of Xia - Tia (in the proof of Theorem 8), and do not need to differentiate between zero and negative values. Invoking Theorem 2 on C+ = x q R |iP +(x) = 0 , yields: i Corollary 10. The number of -/+ sign configurations (where zero is considered negative) of r poly- nomials, each of degree at most d, over q variables, is at most (4edr/q)q (for r > q > 2). Applying Corollary 10 on the nm degree-two polynomials Y k ia U =1 iVa establishes that for any Y , the number of configurations of sign agreements of rank-k matrices with Y is bounded by (8em/k)k(n+m) and yields a constant of 8 instead of 16 inside the logarithm in Theorem 1. Applying Corollary 10 instead of Corollary 3 allows us to similarly tighten in the bounds in Corollary 7 and in Theorem 8. 4A more careful analysis shows that F has pseudodimension three. B Generalization Error Bound in terms of the Pseudodimension Theorem 11. Let F be a class of real-valued functions f : X R with pseudodimension d, and loss : R Y R be a bounded monotone loss function (i.e. for all y, loss(x, y) is mono- tone in x), with loss < M . For any joint distribution over (X, Y ), consider an i.i.d. sample S = (X1, Y1), . . . , (Xn, Yn). Then for any > 0: n d 1 32eM 2 n Pr fF EX,Y [loss(f (X), Y )] > loss(f (Xi), Yi) + < 4e(d + 1) e- 32 S n i=1 The bound is a composition of a generalization error bound in terms of the L1 covering number [17, Theorem 17.1], a bound on the L1 covering number in terms of the pseudodimension [18] and the observation that composition with a monotone function does not increase the pseudodimension [17, Theorem 12.3].

The cut-norm ||A||C of a real matrix A = (aij)i∈R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity | ∑ i∈I,j∈J aij|. This concept plays a major role in the design of efficient approximation algorithms for dense graph and matrix problems. Here we show that the problem of approximating the cut-norm of a given real matrix is MAX SNP hard, and provide an efficient approximation algorithm. This algorithm finds, for a given matrix A = (aij)i∈R,j∈S, two subsets I ⊂ R and J ⊂ S, such that | ∑ i∈I,j∈J aij | ≥ ρ||A||C, where ρ> 0 is an absolute constant satisfying ρ> 0.56. The algorithm combines semidefinite programming with a rounding technique based on Grothendieck’s Inequality. We present three known proofs of Grothendieck’s inequality, with the necessary modifications which emphasize their algorithmic aspects. These proofs contain rounding techniques which go beyond the random hyperplane rounding of Goemans and Williamson [12], allowing us to transfer various algorithms for dense graph and matrix problems to the sparse case. 1

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a $(\frac{1}{2}+o(1)){n \choose 2} $ upper bound and a nearly matching $0.32{n \choose 2}$ lower bound for the minimum possible number of queries. In contrast, if we allow randomness, then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Let X=[1,2,•••,n] be a ground set of n elements, and let S be a family of subsets of X, |S|=m, with a positive cost cS associated with each S ∈ S.Consider the following online version of the set cover problem, described as a game between an algorithm and an adversary. An adversary gives elements to the algorithm from X one-by-one. Once a new element is given, the algorithm has to cover it by some set of S containing it. We assume that the elements of X and the members of S are known in advance to the algorithm, however, the set X' ⊆ X of elements given by the adversary is not known in advance to the algorithm. (In general, X' may be a strict subset of X.) The objective is to minimize the total cost of the sets chosen by the algorithm. Let C denote the family of sets in S that the algorithm chooses. At the end of the game the adversary also produces (off-line) a family of sets COPT that covers X'. The performance of the algorithm is the ratio between the cost of C and the cost of COPT. The maximum ratio, taken over all input sequences, is the competitive ratio of the algorithm.We present an O(log m log n) competitive deterministic algorithm for the problem, and establish a nearly matching Ω(log n log m/log log m + log log n) lower bound for all interesting values of m and n. The techniques used are motivated by similar techniques developed in computational learning theory for online prediction (e.g., the WINNOW algorithm) together with a novel way of converting the fractional solution they supply into a deterministic online algorithm.

Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ε n2 edges have to be deleted from it to make it H-free. We show that in this case G contains at least f(ε,H) nh copies of H. This is proved by establishing a directed version of Szemeredi's regularity lemma, and implies that for every H there is a one-sided error property tester whose query complexity is bounded by a function of ε only for testing the property PH of being H-free.

A set X of points in $\Re^d$ is (k,b)-clusterable if X can be partitioned into k subsets (clusters) so that the diameter (alternatively, the radius) of each cluster is at most b. We present algorithms that, by sampling from a set X, distinguish between the case that X is (k,b)-clusterable and the case that X is $\epsilon$-far from being (k,b')-clusterable for any given $0 < \epsilon\leq 1$ and for $b' \geq b$. By $\epsilon$-far from being (k,b')-clusterable we mean that more than $\epsilon\cdot|X|$ points should be removed from X so that it becomes (k,b')-clusterable. We give algorithms for a variety of cost measures that use a sample of size independent of |X| and polynomial in k and $1/\epsilon$. Our algorithms can also be used to find approximately good clusterings. Namely, these are clusterings of all but an $\epsilon$-fraction of the points in X that have optimal (or close to optimal) cost. The benefit of our algorithms is that they construct an implicit representation of such clusterings in time independent of |X|. That is, without actually having to partition all points in X, the implicit representation can be used to answer queries concerning the cluster to which any given point belongs.

Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The problem consists of statically verifying that the output of every transformation belongs to a given output tree language (specified for XML by a DTD), for input databases satisfying given integrity constraints. The typechecking problem is parameterized by the class of formulas defining the transformation, the class of output tree languages, and the class of integrity constraints. While undecidable in its most general formulation, the typechecking problem has many special cases of practical interest that turn out to be decidable. The main contribution of this article is to trace a fairly tight boundary of decidability for typechecking in this framework. In the decidable cases we examine the complexity, and show lower and upper bounds. We also exhibit a practically appealing restriction for which typechecking is in PTIME.

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0.32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

We present a simple, explicit construction of an infinite family F of bounded-degree 'unique-neighbor' expanders /spl Gamma/; i.e., there are strictly positive constants /spl alpha/ and /spl epsi/, such that all /spl Gamma/ = (X, E(/spl Gamma/)) /spl isin/ F satisfy the following property. For each subset S of X with no more than /spl alpha/|X| vertices, there are at least /spl epsi/|S| vertices in X/spl bsol/S that are adjacent in /spl Gamma/ to exactly one vertex in S. The construction of F is simple to specify, and each /spl Gamma/ /spl isin/ F is 6-regular. We then extend the technique and present easy to describe explicit infinite families of 4-regular and 3-regular unique-neighbor expanders, as well as explicit families of bipartite graphs with nonequal color classes and similar properties. This has several applications and settles an open problem considered by various researchers.

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error εnr. We prove a newgeneral paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, and the optimum value of the subsystem induced on these variables gives (after a direct normalization and with high probability) an approximation to the optimum of the whole system up to an additive error of εnr. Our method gives for the first time a polynomial in ε—1 bound on the sample size necessary to carry out the above approximation. Moreover, this bound is independent in the exponent on the dimension r. The above method gives a completely uniform sampling technique for all the MAX-rCSP problems, and improves the best known sample bounds for the low dimensional problems, like MAX-CUT. The method of solution depends on a new result on t he cut norm of random subarrays, and a new sampling technique for high dimensional linear programs. This method could be also of independent interest.

Let G be a graph on n vertices and suppose that at least $\epsilon n^2$ edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on $c k\,{\rm ln}\,k/ \epsilon^2$ vertices are not k-colorable, where c > 0 is an absolute constant. If G is as above for k=2, then most induced subgraphs on $\frac{({\rm ln} (1/\epsilon))^b}{\epsilon}$ are nonbipartite, for some absolute positive constant b, and this is tight up to the polylogarithmic factor. Both results are motivated by the study of testing algorithms for k-colorability, first considered by Goldreich, Goldwasser, and Ron in, [J. ACM, 45 (1998), pp. 653--750], and improve the results in that paper.

We use a Ramsey-theoretic argument to obtain the first lower bounds for approximations over Z/sub m/ by nonlinear polynomials: (i) A degree-2 polynomial over Z/sub m/ (m odd) must differ from the parity function on at least a 1/2-1/2((log n)/sup /spl Omega/(1)/) fraction of all points in the Boolean n-cube. A degree-O(1) polynomial over Z/sub m/ (m odd) must differ from the parity function on at least a 1/2-o(1) fraction of all points in the Boolean n-cube. These nonapproximability results imply the first known lower bounds on the top fanin of MAJoMOD/sub m/oAND/sub O(1)/ circuits (i.e., circuits with a single majority-gate at the output node, MOD/sub m/-gates at the middle level, and constant-fanin AND-gates at the input level) that compute parity: (i) MAJoMOD/sub m/oAND/sub 2/ circuits that compute parity must have top fanin 2((log n)/sup /spl Omega/(1)/). (ii) Parity cannot be computed by MAJoMODmoAND/sub O(1)/ circuits with top fanin O(1). Similar results hold for the MOD/sub q/ function as well.

Let H be a fixed graph with h vertices, let G be a graph on n vertices and suppose that at least /spl epsi/n/sup 2/ edges have to be deleted from it to make it H-free. It is known that in this case G contains at least f (/spl epsi/, H)n/sup h/ copies of H. We show that the largest possible function f (/spl epsi/, H) is polynomial in /spl epsi/ if and only if H is bipartite. This implies that there is a one-sided error property tester for checking H-freeness, whose query complexity is polynomial in 1//spl epsi/, if and only if H is bipartite.

We consider the standard semi-direct product A/spl times/B of finite groups A, B. We show that with certain choices of generators for these three groups, the Cayley graph of A/spl times/B is (essentially) the zigzag product of the Cayley graphs of A and B. Thus, using the results of O. Reingold et al. (2000), the new Cayley graph is an expander if and only if its two components are. We develop some general ways of using this construction to obtain large constant-degree expanding Cayley graphs from small ones. A. Lubotzky and B. Weiss (1993) asked whether expansion is a group property; namely, is being an expander for (a Cayley graph of) a group G depend solely on G and not on the choice of generators. We use the above construction to answer the question in the negative, by showing an infinite family of groups A/sub i//spl times/B/sub i/ which are expanders with one choice of a (constant-size) set of generators and are not with another such choice. It is interesting to note that this problem is still open, though for "natural" families of groups like the symmetric groups S/sub n/ or the simple groups PSL(2, p).

Motivated by the need to export relational databases as XML data in the context of the World Wide Web, we investigate the type-checking problem for transformations of relational data into tree data (i.e. XML). The problem consists of statically verifying that the output of every transformation belongs to a given output tree language (specified for XML by a document type definition), for input databases satisfying given integrity constraints. The type-checking problem is parameterized by the class of formulas defining the transformation, the class of output tree languages and the class of integrity constraints. While undecidable in its most general formulation, the type-checking problem has many special cases of practical interest that turn out to be decidable. The main contribution of this paper is to trace a fairly tight boundary of decidability for type-checking in this framework. In the decidable cases, we examine the complexity and show lower and upper bounds. We also exhibit a practically appealing restriction for which type-checking is in PTIME.

We investigate the type checking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had been studied by a subset of the authors in a simplified framework that captured the structure of XML documents but ignored data values. We revisit here the type checking problem in the more realistic case when data values are present in documents and tested by queries. In this extended framework, type checking quickly becomes undecidable. However, it remains decidable for large classes of queries and DTDs of practical interest. The main contribution of the present paper is to trace a fairly tight boundary of decidability for type checking with data values. The complexity of type checking in the decidable cases is also considered.

Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and effort required to sequence the DNA in the missing gaps. This procedure has been used in a number of microbial sequencing projects including Streptococcus pneumoniae and other bacteria. In this paper we describe a theoretical framework for this problem and propose an improved method that guarantees to minimize the number of steps involved in the gap closure procedures. In given particular collection of n/2 DNA fragments we describe a strategy that requires. 0.75 log n work in eight parallel rounds of experiment closely matching a corresponding lower bound 0.5 log of n

In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such oligo arrays leads to a combinatorial problem, requiring certain binary codes which have an additional balance property. Constructions using block designs and packings for these codes, within a range of interest in a practical manufacturing application, are developed. The focus is on equireplicate codes, constant weight codes in which every bit position is a one equally often.

Semidefinite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees using local ratio techniques. Are the bounds obtained in this way tight? This problem was considered before by Karloff [SIAM J. Comput., 29 (1999), pp. 336--350] and by Alon and Sudakov [ Combin. Probab. Comput., 9 (2000), pp. 1--12]. Here we further extend their results and show, for the first time, that the local analyses of the Goemans and Williamson MAX CUT algorithm, as well as its extension by Zwick, are tight for every possible relative size of the maximum cut in the sense that the expected value of the solutions obtained by the algorithms may be as small as the analyses ensure. We also obtain similar results for a related problem. Our approach is quite general and could possibly be applied to some additional problems and algorithms.

For any positive integers r and n, let H(r,n) denote the family of graphs on n vertices with maximum degree r, and let H(r,n,n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r,n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r,n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r,n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n,n,p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r,/spl alpha/(/spl alpha/)n,/spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0,1)/spl rarr/(0,1].

A set X of points in /spl Rfr//sup d/ is (k,b)-clusterable if X can be partitioned into k subsets (clusters) so that the diameter (alternatively, the radius) of each cluster is at most b. We present algorithms that by sampling from a set X, distinguish between the case that X is (k,b)-clusterable and the case that X is /spl epsiv/-far from being (k,b')-clusterable for any given 0

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750]. The subject of this paper is testing regular languages. Our main result is as follows. For a regular language $L\in \{0,1\}^*$ and an integer n there exists a randomized algorithm which always accepts a word w of length n if $w\in L$ and rejects it with high probability if w has to be modified in at least $\epsilon n$ positions to create a word in L. The algorithm queries $\tilde{O}(1/\epsilon)$ bits of w. This query complexity is shown to be optimal up to a factor polylogarithmic in $1/\epsilon$. We also discuss the testability of more complex languages and show, in particular, that the query complexity required for testing context-free languages cannot be bounded by any function of $\epsilon$. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Let P be a property of graphs. An /spl epsiv/-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes, with high probability, between the case of G satisfying P and the case that it has to be modified by adding and removing more than /spl epsiv/n/sup 2/ edges to make it satisfy P. The property P is called testable, if for every /spl epsiv/ there exists an /spl epsiv/-test for P whose total number of queries is independent of the size of the input graph. O. Goldreich et al. (1996) showed that certain graph properties admit an /spl epsiv/-test. In this paper we make a first step towards a logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type "/spl forall//spl exist/" are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called /spl epsiv/-unavoidable in G if all graphs that differ from G in no more than /spl epsiv/|G|/sup 2/ places contain an induced copy of H. A graph H is called /spl delta/-abundant in G if G contains at least /spl delta/|G|/sup |H|/ induced copies of H. If H is /spl epsiv/-unavoidable in G then it is also /spl delta/(/spl epsiv/, |H|)-abundant.

We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means.

Query optimizers rely on fast, high-quality estimates of result sizes in order to select between various join plans.Selfjoin sizes of relations provide bounds on the join size of any pairs of such relations.It also indicates the degree of skew in the data, and has been advocated for several estimation procedures.Exact computation of the self-join size requires storage proportional to, the number of distinct attribute values, which may be prohibitively large.In this paper, we study algorithms for tracking (approximate) self-join sizes in limited storage in the presence of insertions and deletions to the relations.Such algorithms detect changes in the degree of skew without an expensive recomputation from the base data.We show that an algorithm based on a tug-ofwar approach provides a more accurate estimation than one based on a sample-and-count approach which is in turn more accurate than a sampling-only approach.Next, we study algorithms for tracking (approximate) join sizes in limited storage; the goal is to maintain a small signature of each relation such that join sizes can be accurately estimated between any pairs of relations.We show that taking random samples for join signatures can lead to inaccurate estimation unless the sample size is quite large; moreover, by a lower bound we show, no other signature scheme can significantly improve upon sampling without further assumptions.These negative results are shown to hold even in the presence of sanity bounds.On the other hand, we present a join signature scheme based on tug-ofwar signatures that probvides guarantees on join size estimation as a function of t:he self-join sizes of the joining relations; this scheme can significantly improve upon the sampling scheme.

Consider the set ℋ of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good ℋ is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from ℋ and look at the expected size of the largest hash bucket. ℋ is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently. If the finite field F has n elements, then there is a bad set S ⊂ F 2 of size n with expected maximal bucket size Ω( n 1/3 ). If n is a perfect square, then there is even a bad set with largest bucket size always at least √n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below √ + 1/2.) If, however, we consider the field of two elements, then we get much better bounds. The best previously known upper bound on the expected size of the largest bucket for this class was O (2 √ log n ). We reduce this upper bound to O (log n log log n ). Note that this is not far from the guarantee for a random function. There, the average largest bucket would be Θ (log n / log log n ). In the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset S of a vector space D over Z 2 , and consider a random linear mapping of D to a smaller vector space R . If the cardinality of S is larger than c ε | R |log| R |, then with probability 1 - ϵ, the image of S will cover all elements in the range.

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or “agnostic”) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.

Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G3n,p,3 with high probability, whenever p $\geq$ c/n, where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p $\geq$ polylog(n)/n [J. Algorithms, 19 (1995), pp. 204--234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c.

Given a set of m coins out of a collection of coins of k unknown distinct weights, the authors wish to decide if all the m given coins have the same weight or not using the minimum possible number of weighings in a regular balance beam. Let m(n,k) denote the maximum possible number of coins for which the above problem can be solved in n weighings. They show that m(n,2)=n/sup ( 1/2 +o(1))n/, whereas for all 3/spl les/k/spl les/n+1, m(n,k) is much smaller than m(n,2) and satisfies m(n,k)=/spl Theta/(n log n/log k). The proofs have an interesting geometric flavour; and combine linear algebra techniques with geometric probabilistic and combinatorial arguments.

The frequency moments of a sequence containing m i elements of type i, for 1 i n, are the numbers Fk = P n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers Fk , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0

We develop an efficient scheme that produces an encoding of a given message such that the message can be decoded from any portion of the encoding that is approximately equal to the length of the message. More precisely, an (n,c,l,r)-erasure-resilient code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r/l packets. We describe erasure-resilient codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.

A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph.

An (n,c,l,r) erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r/l packets. We describe erasure codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.

Given an n × n matrix A = [aij], a transversal of A is a set of elements, one from each row and one from each column. A transversal is a latin transversal if no two elements are the same. Erdös and Spencer showed that there always exists a latin transversal in any n × n matrix in which no element appears more than s times, for s⩽ (n — 1)/16. Here we show that, in fact, the elements of the matrix can be partitioned into n disjoint latin transversals, provided n is a power of 2 and no element appears more than εn times for some fixed ε>0. The assumption that n is a power of 2 can be weakened, but at the moment we are unable to prove the theorem for all values of n.

We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments an

We describe a novel randomized method.the method of cobm-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a gwen graph G = ( 1', E).The randomized algorithms obtained using this method can be derandomlzcd using kmihes of petfect hash f~wtctmns.Using the color-coding method we obtain.m particular, the following new results:-For every fixed k, if a graph G = (V.E) contains a simple cycle of size exactly k, then such a cycle can be found m either 0( V'") expected time or 0( L'"' log P') worst-case t]mc, where w < ?,376 ]s the exponent of matrrx multiplication.(Here and in what follows we use V and E instead of Ib' and IEI whenever no confusion may arise.)-For every fwed k, if a planar graph G = (P-, E) contains a simple cycle of size e.wrctly k, then such a cycle cmr be found m either 0(V) expected time or 0( V log V ) worst-case time.The same algorithm applies, in fact, not only to planar gmphs, but to any mino~closed family of graphs which is not the f~mily of all graphs, -If a grdph G = (V, E) contains a subgraph isomorphic to a boanded tree-width graph H = ( V~, E~) where IV, I = O(log V), then such a copy of H can be found in polyzonzml tune.This was not prewously known even if H were Just a path of length O(log V).These results improve upon previous results of many authors.The third result resolves in the affirmative a conjecture of Papadimltnou and Yannakakis that the LOG PATH problem is m P. We can show that it is even in NC.

This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and the edge player chooses an edge e. The payoff to the edge player is $\textit{cost} (T, e)$, defined as follows: If e lies in the tree T then $\textit{cost}(T, e) = 0$; if e does not lie in the tree then $\textit{cost}(T, e) = cycle(T, e)/w(e)$, where $w(e)$ is the weight of edge e and $\textit{cycle}(T, e)$ is the weight of the unique cycle formed when edge e is added to the tree T. The main result is that the value of the game on any n-vertex graph is bounded above by $\exp(O(\sqrt{\log n \log \log n}))$. It is conjectured that the value of the game is $O(\log n)$. The game arises in connection with the k-server problem on a road network; i.e., a metric space that can be represented as a multigraph G in which each edge e represents a road of length $w(e)$. It is shown that, if the value of the game on G is $\textit{Val}(G, w)$, then there is a randomized strategy that achieves a competitive ratio of $k(1 + \textit{Val}(G, w))$ against any oblivious adversary. Thus, on any n-vertex road network, there is a randomized algorithm for the k-server problem that is $k \cdot \exp(O(\sqrt{\log n \log \log n}))$ competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any n-vertex weighted, connected multigraph, the algorithm constructs a spanning tree T such that the average, over all edges e, of $\textit{cost}(T, e)$ is less than or equal to $\exp(O(\sqrt{\log n \log \log n}))$. This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph.

We study the savings afforded by repeated use in two zero-error communication problems. We show that for some random sources, communicating one instance requires arbitrarily many bits, but communicating multiple instances requires roughly 1 bit per instance. We also exhibit sources where the number of bits required for a single instance is comparable to the source's size, but two instances require only a logarithmic number of additional bits. We relate this problem to that of communicating information over a channel. Known results imply that some channels can communicate exponentially more bits in two uses than they can in one use.>

The Tutte-Grothendieck polynomial T(G; x, y) of a graph G encodes numerous interesting combinatorial quantities associated with the graph. Its evaluation in various points in the (x,y) plane gave the number of spanning forests of the graph, the number of its strongly connected orientations, the number of its proper k-colorings, the (all terminal) reliability probability of the graph, and various other invariants the exact computation of each of which is well known to be P-hard. Here we develop a general technique that supplies fully polynomial randomised approximation schemes for approximating the valve of T(G; x,, y) for any dense graph G, that is, any graph on n vertices whose minimum degree is /spl Omega/(n), whenever x/spl ges/1 and y/spl ges/1, and in various additional points. This region includes evaluations of reliability and partition functions of the ferromagnetic Q-state Potts model. Extensions to linear matroids where T specialises to the weight enumerator of linear codes are considered as well.>

Let G(3n, p, 3) be a random 3-colorable graph on a set of 3n vertices generated as follows.First, split the vertices arbitrarily into three equal color classes and then choose every pair of vertices of distinct color classes, randomly and independently, to be an edge with probability p.We describe a polynomial time algorithm that finds a proper 3coloring of G(3n, p, 3) with high probability, whenever p ~c/n, where c is a sufficiently large absolute constant.This settles a problem of Blum and Spencer, who asked if one can design an algorithm that works almost surely for p ~polylog(n)/n.The algorithm can be extended to produce optimal kcolorings of random k-colorable graphs in a similar model, as well as in various related models.

We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V,E). The randomized algorithms obtained using this method can be derandomized using families of perfect hash functions. Using the color-coding method we obtain, among others, the following new results: • For every fixed k, if a graph G = (V,E) contains a simple cycle of size exactly k, then such a cycle can be found in either O(V ω) expected time or O(V ω log V ) worst-case time, where ω < 2.376 is the exponent of matrix multiplication. (Here and in what follows we use V and E instead of |V | and |E| whenever no confusion may arise.) • For every fixed k, if a planar graph G = (V,E) contains a simple cycle of size exactly k, then ∗Work supported in part by The basic research foundation administrated by The Israel academy of sciences and humanities and by grant No. 93-6-6 of the Sloan foundation. †Institute for Advanced study, school of Mathematics, Princeton, NJ 08540, USA. ‡School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, ISRAEL. E-mail addresses of authors: {noga,raphy,zwick}@math.tau.ac.il. such a cycle can be found in either O(V ) expected time or O(V log V ) worst-case time. The same algorithm applies, in fact, not only to planar graphs, but to any minor closed family of graphs which is not the family of all graphs. • If a graph G = (V,E) contains a subgraph isomorphic to a bounded tree-width graph H = (VH , EH) where |VH | = O(log V ), then such a copy of H can be found in polynomial time. This was not previously known even if H were just a path of length O(log V ). These results improve upon previous results of many authors. The third result resolves in the affirmative a conjecture of Papadimitriou and Yannakakis that the LOG PATH problem is in P. We can even show that the LOG PATH problem is in NC.

For any fixed dimension d , the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O ( n ) processors almost surely in constant time. The algorithm always finds the correct solution. With nd /log 2 d processors, the probability that the algorithm will not finish within O ( d 2 log 2 d ) time tends to zero exponentially with n . — Authors' Abstract

All Boolean variables here range over the two-element set $\{ - 1,1 \}$. Given n Boolean variables $x_1 , \ldots ,x_n $, a nonmonotone MAJORITY gate (in the variables $x_i $) is a Boolean function whose value is the sign of $\Sigma _{i = 1}^n \varepsilon _i x_i $, where each $ \varepsilon _i $ is either 1 or $ - 1$. The COMPARISON function is the Boolean function of two n-bits integers X and Y whose value is $ - 1$ if and only if $X\geqq Y$. An explicit sparse polynomial whose sign computes this function is constructed. Similar polynomials are constructed for computing all the bits of the summation of the two numbers X and Y. This supplies explicit constructions of depth-2 polynomial-size circuits computing these functions, which use only nonmonotone MAJORITY gates. These constructions are optimal in terms of the depth and can be used to obtain the best-known explicit constructions of MAJORITY circuits for other functions like the product of two n-bit numbers and the maximum of nn-bit numbers. A crucial ingredient is the construction of a discrete version of a sparse “delta polynomial”—one that has a large absolute value for a single assignment and extremely small absolute values for all other assignments.

A class of routing problems on connected graphs G is considered. Initially, each vertex v of G is occupied by a “pebble” that has a unique destination $\pi ( v )$ in G (so that $\pi $ is a permutation of the vertices of G). It is required that all the pebbles be routed to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected, and the pebbles at each edge’s endpoints are interchanged. The problem of interest is to minimize the number of steps required for any possible permutation $\pi $. This paper investigates this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs, and Cayley graphs. In addition, this routing problem is related to certain network flow problems, and to several graph invariants including diameter, eigenvalues, and expansion coefficients.

The authors give a short proof of a theorem of Lipton and Tarjan, that, for every planar graph with $n > 0$ vertices, there is a partition $( A,B,C )$ of its vertex set such that $|A|,|B| < \frac{2}{3}n,|C| \leq 2( 2n )^{1/2} $, and no vertex in A is adjacent to any vertex in B Secondly, they apply the same technique more carefully to deduce that, in fact, such a partition $( A,B,C )$ exists with $|A|,|B| < \frac{2}{3}n$, and $|C| \leq \frac{3}{2}( 2n )^{1/2} $ ; this improves the best previously known result. An analogous result holds when the vertices or edges are weighted.

We show that the expected length of any one-to-one encoding of a discrete random variable X is at least H(X)-log(H(X)+1)-log e and that this bound is asymptotically achievable.>

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G={G1,G2,...,Gk} is called a clique cover of G if (i) each Gi is a clique or a bipartite clique, and (ii) the union of Gi is G. The size of the clique cover G is defined as Σki=1 ni, where ni is the number of vertices in Gi. Our main result is that there exist visibility graphs of n nonintersecting line segments in the plane whose smallest clique cover has size Ω(n2/log2n. An upper bound of 0(n2/log n) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of size O(n log3 n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n log n).

We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments and the Euclidean norm: (i) longest non-crossing matching, (ii) longest non-crossing hamiltonian path, (iii) longest non-crossing spanning tree. We propose simple and efficient algorithms to approximate these structures within a constant factor of optimality. Somewhat surprisingly, we also show that our bounds are within a constant factor of optimality even without the non-crossing constraint. For instance, we give an algorithm to compute a non-crossing matching whose total length is at least 2/π of the longest (possibly crossing) matching, and show that the ratio 2/π between the non-crossing and crossing matching is the best possible. Perhaps due to their utter simplicity, our methods also seem more general and amenable to applications in other similar contexts.

Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Gliveako-Cantelli classes. In this paper we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to characterize PAC learnability in the statistical regression framework of probabilistic concepts, solving an open problem posed by Kearns and Schapire. Our characterization shows that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class.>

We consider a class of routing problems on connected graphs G. Initially, each vertex v of G is occupied by a "pebble" which has a unique destination T(V) in G, so that m is a permutation of the vertices of G.It is required to route all the pebbles to their respective destinations by performing a sequence of moves of the following type: A disjoint set of edges is selected and the pebbles at each edge's endpoints are interchanged.The problem of interest is to minimize the number of steps required for any possible permutation m.The odd-even sorting network shows that in the very special case that G is an n-vertex path, any permutation can be routed in n steps.Here we investigate this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs and various Cayley graphs.In addition, we relate this routing problem to certain network flow problems, and to several graph invariants including diameter, eigenvalues and expansion coefficients.Three of our results are the following: (i) Any permutation can be routed on any n-vertex connected graph in less than 3n steps.

Perfect information coin-flipping and leader-election games arise naturally in the study of fault tolerant distributed computing and have been considered in many different scenarios. This paper answers a question of Ben-Or and Linial by proving that for every $c < 1$ there are such games on n players in which no coalition of $cn$ players can influence the outcome with probability greater than some universal constant times c. (Note that this paper actually proves this statement only for all $c < \frac{1}{3}$, but since its universal constant is bigger than 3 the above is trivial for $c \geqslant \frac{1}{3}$.) This paper shows that a random protocol of a certain length has this property and gives an explicit construction as well.

Suppose we are given a sequence of n points v1,…,vn in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. We assume that the points appear one at a time, vi arriving at step i. At the end of step i, the on-line algorithm must construct a connected graph Ti-1. This can be done by joining vi (not necessarily by a straight line) to any point of Ti-1, which need not necessarily be one of the previously given points vj. The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences v1,…,vn as above, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points v1,…, vn. There are known on-line algorithms whose competitive ratio is O(log n), but there is no known nontrivial lower bound for the best possible competitive ratio. Here we prove that the upper bound is almost tight by establishing an Ω(log n/log log n) lower bound for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well.

A family of sets has the (p, q) property if among arty p members of the family some This extends Helly's Theorem and settles an old problem of Hadwiger and Debrunner.

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Ω(d√k)

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition; they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive; they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC/sup 1/.>

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.>

The authors prove a lower bound of Omega (log n/log log n) on the competitive ratio of any (deterministic or randomised) distributed algorithm for solving the mobile user problem on certain networks of n processors. The lower bound holds for various networks, including the hypercube, any network with sufficiently large girth, and any highly expanding graph. A similar Omega (log n/log log n) lower bound is proved for the competitive ratio of the maximum job delay of any distributed algorithm for solving a distributed scheduling problem on any of these networks. The proofs combine combinatorial techniques with tools from linear algebra and harmonic analysis and apply, in particular, a generalization of the vertex isoperimetric problem on the hypercube, which may be of independent interest.>

A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the constructions, the expanders are used to enhance Justesen codes by replicating, shuffling, and then regrouping the code coordinates. For any fixed (small) rate, and for a sufficiently large alphabet, the codes thus obtained lie above the Zyablov bound. Using these codes as outer codes in a concatenated scheme, a second asymptotic good construction is obtained which applies to small alphabets (say, GF(2)) as well. Although these concatenated codes lie below the Zyablov bound, they are still superior to previously known explicit constructions in the zero-rate neighborhood.

The Lovasz local lemma (1975) is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any efficient way of solving the corresponding algorithmic problems. J. Beck has recently found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates, but his method does not seem to be parallelizable. His technique is modified to achieve an algorithmic version that can be parallelized, thus providing deterministic NC/sup 1/ algorithms for various interesting algorithmic search problems.>

Let K ( m ) denote the smallest number with the property that every m -state finite automaton can be built as a neural net using K ( m ) or fewer neurons. A counting argument shows that K ( m ) is at least Ω(( m log m ) 1/3 ), and a construction shows that K ( m ) is at most O ( m 3/4 ). The counting argument and the construction allow neural nets with arbitrarily complex local structure and thus may require neurons that themselves amount to complicated networks. Mild, and in practical situations almost necessary, constraints on the local structure of the network give, again by a counting argument and a construction, lower and upper bounds for K ( m ) that are both linear in m .

The authors present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is O(log log n+k+log 1/ epsilon ), where epsilon is the statistical difference between the distribution induced on any k-bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by J. Naor and M. Naor (1990). An advantage of the present constructions is their simplicity. Two of the constructions are based on bit sequences that are widely believed to possess randomness properties, and the results can be viewed as an explanation and establishment of these beliefs.>

It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solvent on a probabilistic CRCW PRAM (concurrent-read-concurrent-write parallel random-access machine) with O(n) processors almost surely in constant time. The algorithm always finds the correct solution. With nd/log/sup 2/d processors, the probability that the algorithm will not finish within O(d/sup 2/log/sup 2/d) time tends to zero exponentially with n.>

It is proved that for every c>

corresponds to G in time 0(n3/2).We also describe Let G be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H.We prove that there is a set X of no more than h3/2nl/2 vertices of G whose deletion creates a graph in which the total weight of every connected component is at most 1/2.This extends significantly a well-known theorem of Lipton and Tarjan for planar graphs.We exhibit an algorithm which finds, given an n-vertex graph G with weights as above and an h-vertex graph H, either such a set X or a minor of G isomorphic to H.The algorithm runs in time O(hl/2nl/2m), where m is the number of edges of G plus the number of its vertices.Our results supply extensions of the many known applications of the Lipton-Tarjan separator theorem from the class of planar graphs (or that of graphs with bounded genus) to any class of graphs with an excluded minor.For example, it follows that for any fixed graph H, given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/~/l-b-~ in polynomial time, find that size exactly and find the chromatic number of G in time 2 °(¢'~-) and solve any sparse system of n linear equations in n unknowns whose sparsity structure Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.To copy otherwise, or to republish, requires a fee and/or specific

For $n=2^k $, let S be an $n \times n$ matrix whose rows and columns are indexed by $\operatorname{GF}(2)^k $ and, for $i, j \in \operatorname{GF}(2)^k , S_{i.j}=\langle i, j \rangle $, the standard inner product. Size-depth trade-oils are investigated for computing $S{\bf x}$ with circuits using only linear operations. In particular, linear size circuits with depth bounded by the inverse of an Ackerman function are constructed, and it is shown that depth two circuits require $\Omega (n \log n)$ size. The lower bound applies to any Hadamard matrix.

A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then and precisely one of its neighbors transmits. This stringent rule poses serious difficulties in performing even the simplest tasks. This is true even under the overly optimistic assumptions of centralized coordination and complete knowledge of the network topology. This paper is concerned with lower and upper bounds for the complexity of realizing various communication primitives for radio networks.

Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest ${n / 2}$, where in each round one is allowed to ask n binary comparisons. It is shown that $\log ^ * n + \Theta (1)$ rounds are both necessary and sufficient in the best algorithm for this problem.

The authors consider that they have n elements from a totally ordered domain and are allowed to perform p parallel comparisons in each time unit (round). They determine, up to a constant factor, the time complexity of several approximation problems in the common parallel comparison tree model of L.G. Valiant, for all admissible values of n, p, and epsilon , where epsilon is an accuracy parameter determining the quality of the required approximation. The problems considered include the approximate maximum problem, approximate sorting, and approximate merging. The results imply, as special cases, all the known results about the time complexity of parallel sorting, parallel merging, and parallel selection of the maximum (in the comparison model). They highlight one very special but representative result concerning the approximate maximum problem. They wish to find, among the given n elements, one which belongs to the biggest n/2, where in each round they are allowed to ask n binary comparisons. They show that log/sup */n+ Theta (1) rounds are both necessary and sufficient in the best algorithm for this problem.>

In practice, the average time of (deterministic or randomized) sorting algorithms seems to be more relevant than the worst-case time of deterministic algorithms. Still, the many known complexity bounds for parallel comparison sorting include no nontrivial lower bounds for the average time required to sort by comparisons n elements with p processors (via deterministic or randomized algorithms). We show that for $p \geqq n$ this time is $\Theta ({{\log n} / {\log (1 + {p / n})}})$ (it is easy to show that for $p \leqq n$ the time is $\Theta ({{n\log n} / {({p / n})}})$. Therefore even the average-case behaviour of randomized algorithms is not more efficient than the worst-case behaviour of deterministic ones.

The worst case number of comparisons needed for sorting or selecting in rounds is considered. The following results are obtained. (a) For every fixed $k\geqq 2$, $\Omega ( n^{1 + 1/k} ( \log n )^{1/k} )$ comparisons are required to sort n elements in k rounds. ($O ( n^{1 + 1 / k} \log n )$ are known to be sufficient.) This improves the previous known bounds by a factor of $( \log n )^{1/k} $, which separates deterministic algorithms from randomized ones, as there are randomized algorithms whose expected number of comparisons is $O ( n^{1 + 1/k} )$. (b) For every fixed $k\geqq 2$, $\Omega ( n^{1 + 1/( 2^k - 1 )} ( \log n )^{2/( 2^k - 1 )} )$ comparisons are required to select the median from n elements in k rounds. ($O ( n^{1 + 1/ ( 2^k - 1 ) } ( \log n )^{2 - 2/ ( 2^k - 1 ) } )$ are known to be sufficient.) This improves the previous known bounds by a factor of $( \log n )^{2/( 2^k - 1 )} $ and separates the problem of finding the median from that of finding the minimum, as $O( n^{1 + 1/( 2^k - 1 ) } )$ comparisons suffice for finding the minimum. (c) We show that “approximate sorting” in one round requires asymptotically more than $c \cdot n\log n$ comparisons, for every constant c, and can be done in $O\left( {n\log n\log \log n} \right)$ comparisons. This settles a problem raised by Rabin.

For n>0, d>or=0, n identical to d (mod 2), let K(n, d) denote the minimal cardinality of a family V of +or-1 vectors of dimension n, such that for any +or-1 vector w of dimension n there is a v in V such that mod v-w mod>

Article Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension Share on Authors: N. Alon Department of Mathematics, Tel Aviv University, Ramat Aviv, TEL Aviv 69978, Israel Department of Mathematics, Tel Aviv University, Ramat Aviv, TEL Aviv 69978, IsraelView Profile , D. Haussler Computer Science Department, University of California at Santa Cruz, Santa Cruz, CA, USA Computer Science Department, University of California at Santa Cruz, Santa Cruz, CA, USAView Profile , E. Welzl Institutes for Information Processing, Technical University of Graz, Schiesstattgaser 4a, A-8010 GRAZ, Austria Institutes for Information Processing, Technical University of Graz, Schiesstattgaser 4a, A-8010 GRAZ, AustriaView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 331–340https://doi.org/10.1145/41958.41994Online:01 October 1987Publication History 22citation296DownloadsMetricsTotal Citations22Total Downloads296Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In practice, the average time of (deterministic or randomized) sorting algorithms seems to be more relevant than the worst case time of deterministic algorithms. Still, the many known complexity bounds for parallel comparison sorting include no nontrivial lower bounds for the average time required to sort by comparisons n elements with p processors (via deterministic or randomized algorithms). We show that for p ≥ n this time is Θ (log n/log(1 + p/n)), (it is easy to show that for p ≤ n the time is Θ (n log n/p) = Θ (log n/(p/n)). Therefore even the average case behaviour of randomized algorithms is not more efficient than the worst case behaviour of deterministic ones.

The time complexity of sorting n elements using p ≥ n processors on Valiant's parallel comparison tree model is considered. The following results are obtained. 1. We show that this time complexity is Θ(logn/log(1+p/n)). This complements the AKS sorting network in settling the wider problem of comparison sort of n elements by p processors, where the problem for p ≤ n was resolved. To prove the lower bound, we show that to achieve time k ≤ logn, we need Ω(kn1+1/k) comparisons. Häggkvist and Hell proved a similar result only for fixed k. 2. For every fixed time k, we show that: (a) Ω(n1+1/k lognl/k) comparisons are required, (O(n1+1/k logn) are known to be sufficient in this case), and (b) there exists a randomized algorithm for comparison sort in time k with an expected number of O(n1+1/k) comparisons. This implies that for every fixed k, any deterministic comparison sort algorithm must be asymptotically worse than this randomized algorithm. The lower bound improves on Häggkvist-Hell's lower bound. 3. We show that "approximate sorting" in time 1 requires asymptotically more than nlogn processors. This settles a problem raised by M. Rabin.

A novel technique for obtaining lower bounds for the time versus space complexity of certain functions in a general input oblivious sequential model of computation is developed. This is demonstrated by studying the intrinsic complexity of the following set equality problem SE(n,m): Given a sequence x1,x2,....,xn, y1,....,yn of 2n numbers of m bits each, decide whether the sets [x1,....,xn] and [y1,...,yn] coincide. We show that for any log log n ≤ m ≤1/2log n and any 1 ≤ s ≤ log n, any input oblivious sequential computation that solves SE(n,m) using 2m/s space, takes Ω(n ? s) time. This result is sharp for all admissible values of n,m,s and is the first known nontrivial time space tradeoff lower bound (for space = ω (log n) of a set recognition problem on such a general model of computation. Our method also supplies lower bounds on the length of arbitrary (not necessarily input oblivious) branching programs for several natural symmetric functions, improving results of Chandra, Furst and Lipton, of Pudlák and of Ajtai et. al. For example we show that for the majority - function any branching program of width w(n) has length ω(n · log w/n (n) · log w (n)), in particular for bounded width we get length ω (n log n) (independently of our work Babai et. al. [BPRS] have simultaneously proved this last result). Our lower bounds for branching programs imply lower bounds on the number of steps that are needed to pebble arbitrary computation graphs for the same computational problems. To establish our lower bounds we introduce the new concept of a meander that captures superconcentrator-type properties of sequences. We prove lower bounds on the length of meanders via a new Ramsey theoretic lemma that is of interest in its own right. This lemma has other applications, including a tight lower bound on the size of weak superconcentrators of depth 2 that strengthens the known lower bound of Pippenger [Pi]. A surprising new feature of these applications of Ramsey theory in lower bound arguments is the fact that no numbers are required to be unusually large and that several of the resulting superlinear lower bounds are in fact optimal.

Let d = d(n) be the minimum d such that for every sequence of n subsets F1, F2, . . . , Fn of {1, 2, . . . , n} there exist n points P1, P2, . . . , Pn and n hyperplanes H1, H2 .... , Hn in Rd such that Pj lies in the positive side of Hi iff j ∈ Fi. Then n/32 ≤ d(n) ≤ (1/2 + 0(1)) · n. This implies that the probabilistic unbounded-error 2-way complexity of almost all the Boolean functions of 2p variables is between p-5 and p, thus solving a problem of Yao and another problem of Paturi and Simon. The proof of (1) combines some known geometric facts with certain probabilistic arguments and a theorem of Milnor from real algebraic geometry.

Expanding graphs and superconcentrators are relevant to theoretical computer science in several ways. Here we use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges.Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using O(nak) processors, where, e.g., a2 = 7/4.Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with O(n4/3) edges; better than the previous known results.

Explicit construction of families of linear expanders and superconcentrators is relevant to theoretical computer science in several ways. There is essentially only one known explicit construction. Here we show a correspondence between the eigenvalues of the adjacency matrix of a graph and its expansion properties, and combine it with results on Group Representations to obtain many new examples of families of linear expanders. We also obtain better expanders than those previously known and use them to construct explicitly n-superconcentrators with 157.4 n edges, much less than the previous most economical construction.