6 papers
Conditional Encryption with Applications to Secure Personalized Password Typo Correction
Mohammad Hassan Ameri, Jeremiah Blocki
We introduce the notion of a conditional encryption scheme as an extension of public key encryption. In addition to the standard public key algorithms (, $\mathsf{Enc}…
Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
Alexander R. Block, Jeremiah Blocki, Kuan Cheng +4
Locally Decodable Codes (LDCs) are error-correcting codes encoding \emph{messages} in to \emph{codewords} in , with super-fast decoding…
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…
Amortized Locally Decodable Codes for Insertions and Deletions
Jeremiah Blocki, Justin Zhang
Locally Decodable Codes (LDCs) are error correcting codes which permit the recovery of any single message symbol with a low number of queries to the codeword (the locality). Tradit…
Amortized Locally Decodable Codes
Jeremiah Blocki, Justin Zhang
Locally Decodable Codes (LDCs) are error correcting codes that admit efficient decoding of individual message symbols without decoding the entire message. Unfortunately, known LDC…
Differential privacy and Sublinear time are incompatible sometimes
Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu +1
Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differen…