All reports by Author Raghu Meka:

__
TR23-180
| 17th November 2023
__

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka#### New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

__
TR22-148
| 11th November 2022
__

Peter Ivanov, Raghu Meka, Emanuele Viola#### Efficient resilient functions

__
TR21-047
| 26th March 2021
__

Zander Kelley, Raghu Meka#### Random restrictions and PRGs for PTFs in Gaussian Space

Revisions: 1

__
TR20-055
| 22nd April 2020
__

Ashutosh Kumar, Raghu Meka, David Zuckerman#### Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

__
TR19-079
| 28th May 2019
__

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka#### Average Bias and Polynomial Sources

Revisions: 2

__
TR18-200
| 29th November 2018
__

Ashutosh Kumar, Raghu Meka, Amit Sahai#### Leakage-Resilient Secret Sharing

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

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

Peter Ivanov, Raghu Meka, Emanuele Viola

An $n$-bit boolean function is resilient to coalitions of size $q$

if no fixed set of $q$ bits is likely to influence the value of the

function when the other $n-q$ bits are chosen uniformly at random,

even though the function is nearly balanced. We construct explicit

functions resilient to ...
more >>>

Zander Kelley, Raghu Meka

A polynomial threshold function (PTF) $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function of the form $f(x) = sign(p(x))$ where $p$ is a polynomial of degree at most $d$. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address ... more >>>

Ashutosh Kumar, Raghu Meka, David Zuckerman

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

Ashutosh Kumar, Raghu Meka, Amit Sahai

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some ``leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an ... more >>>