Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with combinatorial:
TR13-134 | 25th September 2013
Or Meir

Combinatorial PCPs with Short Proofs

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

TR23-180 | 17th November 2023
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic $O(n^\omega)$ time, where $\omega<3$; much work has gone into bringing $\omega$ closer to $2$. Since then, a ... more >>>

ISSN 1433-8092 | Imprint