PreviousNext

__
TR24-148
| 5th October 2024
__

Swastik Kopparty, Mrinal Kumar, Harry Sha#### High Rate Multivariate Polynomial Evaluation Codes

__
TR24-147
| 4th October 2024
__

Shanthanu Rai#### Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

__
TR24-146
| 27th September 2024
__

Zhenjian Lu, Noam Mazor, Igor Oliveira, Rafael Pass#### Lower Bounds on the Overhead of Indistinguishability Obfuscation

PreviousNext

Swastik Kopparty, Mrinal Kumar, Harry Sha

The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|U|$. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes ... more >>>

Shanthanu Rai

We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree $d$ over finite field $\mathbb{F}_q$. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time $\tilde{O}(d^4 \log^4{q})$.

Our construction extends Shoup's deterministic algorithm ... more >>>

Zhenjian Lu, Noam Mazor, Igor Oliveira, Rafael Pass

We consider indistinguishability obfuscation (iO) for multi-output circuits $C:\{0,1\}^n\to\{0,1\}^n$ of size s, where s is the number of AND/OR/NOT gates in C. Under the worst-case assumption that NP $\nsubseteq$ BPP, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size $s + o(s/ \log s)$. ... more >>>

PreviousNext