Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with preprocessing:
TR05-009 | 14th December 2004
David P. Woodruff, Sergey Yekhanin

A Geometric Approach to Information-Theoretic Private Information Retrieval

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>

TR20-112 | 8th June 2020
Joshua Blinkhorn

Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies

Dependency quantified Boolean formulas (DQBF) describe an NEXPTIME-complete generalisation of QBF, which in turn generalises SAT. QRAT is a recently proposed proof system for quantified Boolean formulas (QBF), which simulates the full suite of QBF preprocessing techniques and thus forms a uniform proof checking format for solver verification.

In this ... more >>>

ISSN 1433-8092 | Imprint