Michal Parnas

MFCS Conference 2022 Conference Paper

On the Binary and Boolean Rank of Regular Matrices

• Ishay Haviv
• Michal Parnas

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^Ω̃(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^Ω̃(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^Ω̃(log k).

TCS Journal 2007 Journal Article

Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms

• Michal Parnas
• Dana Ron

For a given graph G over n vertices, let OPT G denote the size of an optimal solution in G of a particular minimization problem (e. g. , the size of a minimum vertex cover). A randomized algorithm will be called an α -approximation algorithm with an additive error for this minimization problem if for any given additive error parameter ϵ > 0 it computes a value OPT ˜ such that, with probability at least 2 / 3, it holds that OPT G ≤ OPT ˜ ≤ α ⋅ OPT G + ϵ n. Assume that the maximum degree or average degree of G is bounded. In this case, we show a reduction from local distributed approximation algorithms for the vertex cover problem to sublinear approximation algorithms for this problem. This reduction can be modified easily and applied to other optimization problems that have local distributed approximation algorithms, such as the dominating set problem. We also show that for the minimum vertex cover problem, the query complexity of such approximation algorithms must grow at least linearly with the average degree d ̄ of the graph. This lower bound holds for every multiplicative factor α and small constant ϵ as long as d ̄ = O ( n / α ). In particular this means that for dense graphs it is not possible to design an algorithm whose complexity is o ( n ).

I&C Journal 2003 Journal Article

Testing metric properties

• Michal Parnas
• Dana Ron

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 ϵ, 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 at least 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. We describe algorithms for testing Euclidean metrics, tree metrics and ultrametrics. Furthermore, we present an algorithm that tests whether a matrix M is an approximate ultrametric. In all cases the query complexity and running time are polynomial in 1/ϵ and independent of the size of the matrix. Finally, our algorithms can be used to solve relaxed versions of the corresponding search problems in time that is sub-linear in the size of the matrix.

STOC Conference 2001 Conference Paper

Testing metric properties

• Michal Parnas
• Dana Ron

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. We describe algorithms for testing Euclidean metrics, tree metrics and ultrametrics. Furthermore, we present an algorithm that tests whether a matrix M is an approximate ultrametric. In all cases the query complexity and running time are polynomial in 1 ε and independent of the size of the matrix. Finally, our algorithms can be used to solve relaxed versions of the corresponding search problems in time that is sub-linear in the size of the matrix.

SODA Conference 2000 Conference Paper

Efficient dynamic traitor tracing

• Omer Berkman
• Michal Parnas
• Jirí Sgall

FOCS Conference 2000 Conference Paper

Testing of Clustering

• Noga Alon
• Seannie Dar
• Michal Parnas
• Dana Ron

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</spl epsiv//spl les/1 and for b'/spl ges/b. In /spl epsiv/-far from being (k, b')-clusterable we mean that more than /spl epsiv/. |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//spl epsiv/. Our algorithms can also be used to find approximately good clusterings. Namely, these are clusterings of all but an /spl epsiv/-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 any given point belongs to.

FOCS Conference 1994 Conference Paper

Multi-Index Hashing for Information Retrieval

• Daniel H. Greene
• Michal Parnas
• F. Frances Yao

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. >

SODA Conference 1994 Conference Paper

Neighborhood Preserving Hashing and Approximate Queries

• Danny Dolev
• Yuval Harari
• Nati Linial
• Noam Nisan
• Michal Parnas