Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Guy Moshkovitz:

TR20-029 | 6th March 2020
Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

Geometric Rank of Tensors and Subrank of Matrix Multiplication

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the ... more >>>

TR15-019 | 3rd February 2015
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing Near Spanning Trees with Few Local Inspections

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

TR11-138 | 24th October 2011
Guy Moshkovitz

Complexity Lower Bounds through Balanced Graph Properties

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>

ISSN 1433-8092 | Imprint