We initiate the study of the binary and Boolean rank of 0 , 1 matrices that have a small rank over the reals. The relationship between these three rank functions is an important open question, and here we prove that when the real rank d is a small constant, the gap between the real and the binary and Boolean rank is a small constant. We give tight upper and lower bounds on the Boolean and binary rank of matrices with real rank 1 ≤ d ≤ 4 , as well as determine the size of the largest isolation set in each case. Furthermore, we prove that for d = 3 , 4 , the circulant matrix defined by a row with d − 1 consecutive ones followed by d − 1 zeros, is the only matrix, up to a permutation of the rows and columns and the transpose operation, of size ( 2 d − 2 ) × ( 2 d − 2 ) with real rank d and Boolean and binary rank and isolation set of size 2 d − 2 , and this matrix achieves the maximal gap possible between the real and the binary and Boolean rank for these values of d . Our results can also be interpreted in other equivalent forms, such as finding the minimum number of bicliques needed to partition or cover the edges of a bipartite graph whose reduced adjacency matrix has real rank 1 ≤ d ≤ 4 . We use a combination of combinatorial and algebraic techniques combined with the assistance of a computer program.

A set family F is called intersecting if every two members of F intersect, and it is called uniform if all members of F share a common size. A uniform family F ⊆ binom([n],k) of k-subsets of [n] is ε-far from intersecting if one has to remove more than ε ⋅ binom(n,k) of the sets of F to make it intersecting. We study the property testing problem that given query access to a uniform family F ⊆ binom([n],k), asks to distinguish between the case that F is intersecting and the case that it is ε-far from intersecting. We prove that for every fixed integer r, the problem admits a non-adaptive two-sided error tester with query complexity O((ln n)/ε) for ε ≥ Ω((k/n)^r) and a non-adaptive one-sided error tester with query complexity O((ln k)/ε) for ε ≥ Ω((k²/n)^r). The query complexities are optimal up to the logarithmic terms. For ε ≥ Ω((k²/n)²), we further provide a non-adaptive one-sided error tester with optimal query complexity of O(1/ε). Our findings show that the query complexity of the problem behaves differently from that of testing intersectingness of non-uniform families, studied recently by Chen, De, Li, Nadimpalli, and Servedio (ITCS, 2024).

A $0,1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$, there exists a square regular $0,1$ matrix with binary rank $k$, such that the Boolean rank of its complement is $k^{\widetildeΩ(\log k)}$. Equivalently, the ones in the matrix can be partitioned into $k$ combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is $k^{\widetildeΩ(\log k)}$. This settles, in a strong form, a question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain, and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers $k$, there exists a regular graph with biclique partition number $k$ and chromatic number $k^{\widetildeΩ(\log k)}$.

The Boolean rank of a 0,1-matrix A, denoted Rb(A), is the smallest number of monochromatic combinatorial rectangles needed to cover the 1-entries of A. In 1988, de Caen, Gregory, and Pullman asked if the Boolean rank of the Kronecker product Cn ® Cn is strictly smaller than the square of RB(Cn), where Cn is the n x n matrix with zeros on the diagonal and ones everywhere else (Carib. Conf. Comb. & Comp., 1988). A positive answer was given by Watts for n = 4 (Linear Alg. and its Appl., 2001). A result of Karchmer, Kushilevitz, and Nisan, motivated by direct-sum questions in non-deterministic communication complexity, implies that the Boolean rank of Cn ® Cn grows linearly in that of Cn (SIAM J. Disc. Math., 1995), and thus Rb(Cn ® Cn) < RB(Cn)2 for every sufficiently large n. Their proof relies on a probabilistic argument. In this work, we present a general method for proving upper bounds on the Boolean rank of Kronecker products of 0,1-matrices. We use it to affirmatively settle the question of de Caen et al. for all integers n > 7. We further provide an explicit construction of a cover of Cn ® Cn, whose number of rectangles nearly matches the optimal asymptotic bound. Our method for proving upper bounds on the Boolean rank of Kronecker products might find applications in different settings as well. We express its potential applicability by extending it to the wider framework of spanoids, recently introduced by Dvir, Gopi, Gu, and Wigderson (SIAM J. Comput., 2020).

Convex and submodular functions play an important role in many applications, and in particular in combinatorial optimization. Here we study two special cases: convexity in one dimension and submodularity in two dimensions. The latter type of functions are equivalent to the well-known Monge matrices. A matrix $V = \{v_{i,j}\}_{i,j=0}^{i=n_1,j=n_2}$ is called a Monge matrix if for every $0 \leq i < i' \leq n_1$ and $0 \leq j < j' \leq n_2$ we have $v_{i,j}+v_{i',j'} \le v_{i,j'}+v_{i',j}$. If inequality holds in the opposite direction, then V is an inverse Monge matrix (supermodular function). Many problems, such as the traveling salesperson problem and various transportation problems, can be solved more efficiently if the input is a Monge matrix. In this work we present testing algorithms for the above properties. A testing algorithm for a predetermined property $\cal P$ is given query access to an unknown function f and a distance parameter $\epsilon$. The algorithm should accept f with high probability if it has the property $\cal P$ and reject it with high probability if more than an $\epsilon$-fraction of the function values should be modified so that f obtains the property. Our algorithm for testing whether a 1-dimensional function $f:[n] \rightarrow \mathbb{R}$ is convex (concave) has query complexity and running time of $O\left((\log n) /\epsilon\right)$. Our algorithm for testing whether an n 1 × n 2 matrix V is a Monge (inverse Monge) matrix has query complexity and running time of $O\left((\log n_1\cdot\log n_2) /\epsilon\right)$.

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.

We consider the problem of determining whether a given function $f:{\{0,1\}}^n\to{\{0,1\}}$ belongs to a certain class of Boolean functions $\cal F$ or whether it is far from the class. More precisely, given query access to the function f and given a distance parameter $\epsilon$, we would like to decide whether $f \in \cal F$ or whether it differs from every $g\in \cal F$ on more than an $\epsilon$-fraction of the domain elements. The classes of functions we consider are singleton ("dictatorship") functions, monomials, and monotone disjunctive normal form functions with a bounded number of terms. In all cases we provide algorithms whose query complexity is independent of n (the number of function variables), and linear in $1/\epsilon$.

Finite metric spaces, and in particular tree metrics play an important role in various disciplines such as evolutionary biology and statistics. A natural family of problems concerning metrics is deciding, given a matrix M, whether or not it is a distance metric of a certain predetermined type. Here we consider the following relaxed version of such decision problems: For any given matrix M and parameter \eps, we are interested in determining, by probing M, whether M has a particular metric property P, or whether it is ε far from having the property. In ε far we mean that more than an ε-fraction of the entries of M must be modified so that it obtains the property. The algorithm may query the matrix on entries M[i,j] of its choice, and is allowed a constant probability of error.

Let $D \subseteq \Sigma^n$ be a dictionary. We look for efficient data structures and algorithms to solve the following approximate query problem: Given a query $u \in \Sigma^n$ list all words $v \in D$ that are close to u in Hamming distance. The problem reduces to the following combinatorial problem: Hash the vertices of the n-dimensional hypercube into buckets so that (1) the c-neighborhood of each vertex is mapped into at most k buckets and (2) no bucket is too large. Lower and upper bounds are given for the tradeoff between k and the size of the largest bucket. These results are used to derive bounds for the approximate query problem.

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

The notion of traitor tracing was introduced by Chor, Fiat, and Naor [Tracing Traitors, Lecture Notes in Comput. Sci. 839, 1994, pp. 257--270] in order to combat piracy scenarios. Recently, Fiat and Tassa [ Tracing Traitors, Lecture Notes in Comput. Sci. 1666, 1999, pp. 354--371] proposed a dynamic traitor tracing scenario, in which the algorithm adapts dynamically according to the responses of the pirate. Let n be the number of users and p the number of traitors. Our main result is an algorithm which locates p traitors, even if p is unknown, using a watermarking alphabet of size p+1 and an optimal number of $\Theta(p^2 + p\log n)$ rounds. This improves the exponential number of rounds achieved by Fiat and Tassa in this case. We also present two algorithms that use a larger alphabet: for an alphabet of size p+c+1, $c\geq1$, an algorithm that uses O(p 2 /c+ p log n) rounds; for an alphabet of size pc+1, an algorithm that uses O(p log c n ) rounds. Our final result is a lower bound of $\Omega(p^2/c+p\log_{c+1}n)$ rounds for any algorithm that uses an alphabet of size p+c, assuming that p is not known in advance.

We present fast and efficient parallel algorithms for finding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm runs in O(log n) time using $(m+n^{1+\epsilon})/\log n$ EREW processors (for any fixed $\epsilon > 0$). A variant uses (m+n)/log n processors and runs in O(log n log log n) time. A deterministic version of the algorithm runs in $O(\log^{1.5}n)$ time using m+n EREW processors.

We describe a technique for building hash indices for a large dictionary of strings. This technique permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors. This technique is closely related to the classical Turan problem for hypergraphs. We propose a general method of multi-index construction by generalizing certain Turan hypergraphs. We also develop an accompanying theory for analyzing such hashing schemes. The resulting algorithms have been implemented and can be applied to a wide variety of recognition and retrieval problems.>

We present fast and ecient parallel algorithms for nding the connected components of an undirected graph. These algorithms run on the exclusive-read, exclusive-write (EREW) PRAM. On a graph with n vertices and m edges, our randomized algorithm runs in O(log n) time using (m+n 1+) = logn EREW processors (for any xed > 0). A variant uses (m+n) = logn processors and runs in O(log n log logn) time. A deterministic version of the algorithm runs in O(log 1:5 n) time using m+ n EREW processors. 1