Next

__
TR20-022
| 19th February 2020
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Error Resilience Beyond $\frac{2}{7}$

__
TR20-021
| 21st February 2020
__

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira#### NP-Hardness of Circuit Minimization for Multi-Output Functions

__
TR20-020
| 21st February 2020
__

Nikhil Mande, Justin Thaler, Shuchen Zhu#### Improved Approximate Degree Bounds For $k$-distinctness

Next

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?

For the non-adaptive channel, where the parties must agree ... more >>>

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

Nikhil Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

Next