Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-138 | 5th October 2022
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang

Robustness for Space-Bounded Statistical Zero Knowledge

Revisions: 3

We show that the space-bounded Statistical Zero Knowledge classes SZK_L and NISZK_L are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class. Coupled with other recent characterizations of these classes, this can be viewed as lending support to ... more >>>


TR22-137 | 26th September 2022
Daniel Avraham , Amir Yehudayoff

On blocky ranks of matrices

A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>>


TR22-136 | 21st September 2022
Sepehr Assadi, Gillat Kol, Zhijun Zhang

Rounds vs Communication Tradeoffs for Maximal Independent Sets

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint