Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with random matrices:
TR16-058 | 12th April 2016
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.
This yields a nearly tight ... more >>>

TR20-156 | 22nd October 2020
Sankeerth Rao Karingula, Shachar Lovett

Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

ISSN 1433-8092 | Imprint