𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Nonapproximability of Non-Boolean Predicates

✍ Scribed by Engebretsen, Lars

Book ID
118199523
Publisher
Society for Industrial and Applied Mathematics
Year
2004
Tongue
English
Weight
217 KB
Volume
18
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The Boolean Algebra of Predicates
The Boolean Algebra of Predicates
✍ Martin KΓΌhnrich πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 416 KB
On the Limits of Nonapproximability of L
On the Limits of Nonapproximability of Lattice Problems
✍ Oded Goldreich; Shafi Goldwasser πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 221 KB

We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor ofn, of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP di

Non-cancellative Boolean circuits: A gen
Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
✍ Rimli Sengupta; H. Venkateswaran πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 128 KB

Cancellations are known to be helpful in e cient algebraic computation of polynomials over ΓΏelds. We deΓΏne a notion of cancellation in Boolean circuits and deΓΏne Boolean circuits that do not use cancellation to be non-cancellative. Non-cancellative Boolean circuits are a natural generalization of mo