Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Chinese Remainder Theorem:
TR00-012 | 14th February 2000
Ke Yang

Integer Circuit Evaluation is PSPACE-complete

In this paper, we address the problem of evaluating the
Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over
the set of natural numbers. The problem is a natural extension
to the integer expression by Stockmeyer and Mayer, and is also studied
by Mckenzie, Vollmer and Wagner in ... more >>>

TR07-021 | 5th March 2007
Brett Hemenway, Rafail Ostrovsky

Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Revisions: 3

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code.
In particular, our construction simultaneously satisfies all of the following properties:
Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption
... more >>>

TR18-026 | 7th February 2018
Lijie Chen

On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Revisions: 1

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets $A$ and $B$ of vectors, and the goal is to find $a \in A$ and $b \in B$ maximizing inner product $a \cdot b$. Max-IP is very basic and serves ... more >>>

ISSN 1433-8092 | Imprint