Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR14-031 | 16th February 2014
Joao Marques-Silva, Mikolas Janota

On the Query Complexity of Selecting Few Minimal Sets

Propositional Satisfiability (SAT) solvers are routinely used for
solving many function problems.

A natural question that has seldom been addressed is: what is the
best worst-case number of calls to a SAT solver for solving some
target function problem?

This paper develops tighter upper bounds on the query complexity of
more >>>


TR14-030 | 5th March 2014
Dana Moshkovitz

An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing

The Sliding Scale Conjecture in PCP states that there are PCP verifiers with a constant number of queries and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in ... more >>>


TR14-029 | 4th March 2014
Oded Goldreich, Dana Ron

On Learning and Testing Dynamic Environments

Revisions: 3

We initiate a study of learning and testing dynamic environments,
focusing on environment that evolve according to a fixed local rule.
The (proper) learning task consists of obtaining the initial configuration
of the environment, whereas for non-proper learning it suffices to predict
its future values. The testing task consists of ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint