PreviousNext

__
TR22-131
| 18th September 2022
__

Rafael Mendes de Oliveira, Akash Sengupta#### Radical Sylvester-Gallai for Cubics

__
TR22-130
| 15th September 2022
__

Hamed Hatami, Kaave Hosseini, Xiang Meng#### A Borsuk-Ulam lower bound for sign-rank and its application

__
TR22-129
| 15th September 2022
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Binary Codes with Resilience Beyond 1/4 via Interaction

PreviousNext

Rafael Mendes de Oliveira, Akash Sengupta

Let $\mathcal{F} = \{F_1, \ldots, F_m\}$ be a finite set of irreducible homogeneous multivariate polynomials of degree at most $3$ such that $F_i$ does not divide $F_j$ for $i\neq j$.

We say that $\mathcal{F}$ is a cubic radical Sylvester-Gallai configuration if for any two distinct $F_i,F_j$ there exists a ...
more >>>

Hamed Hatami, Kaave Hosseini, Xiang Meng

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>

PreviousNext