Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with algorithm design:
TR12-067 | 6th May 2012
Xiaohui Bei, Ning Chen, Shengyu Zhang

On the Complexity of Trial and Error

Revisions: 1

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>>

TR19-106 | 12th August 2019
Noah Fleming, Pravesh Kothari, Toniann Pitassi

Semialgebraic Proofs and Efficient Algorithm Design

Revisions: 4

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>

ISSN 1433-8092 | Imprint