On the pseudo-deterministic query complexity of NP search problems
We study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF inst...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2021
|
| _version_ | 1797064978456379392 |
|---|---|
| author | Goldwasser, S Impagliazzo, R Pitassi, T Santhanam, R |
| author_facet | Goldwasser, S Impagliazzo, R Pitassi, T Santhanam, R |
| author_sort | Goldwasser, S |
| collection | OXFORD |
| description | We study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF instances, and also for the promise problem (FIND1) of finding a 1 in a vector populated with at least half one’s. This gives an exponential separation between randomized query complexity and pseudo-deterministic complexity, which is tight in the quantum setting. As applications we partially solve a related combinatorial coloring problem, and we separate random tree-like Resolution from its pseudo-deterministic version. In contrast to our lower bound, we show, surprisingly, that in the zero-error, average case setting, the three notions (deterministic, randomized, pseudo-deterministic) collapse. |
| first_indexed | 2024-03-06T21:22:03Z |
| format | Conference item |
| id | oxford-uuid:41c51f17-d355-4afd-ae7f-1c002c7d2fe8 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:22:03Z |
| publishDate | 2021 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:41c51f17-d355-4afd-ae7f-1c002c7d2fe82022-03-26T14:45:48ZOn the pseudo-deterministic query complexity of NP search problemsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:41c51f17-d355-4afd-ae7f-1c002c7d2fe8EnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik 2021Goldwasser, SImpagliazzo, RPitassi, TSanthanam, RWe study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF instances, and also for the promise problem (FIND1) of finding a 1 in a vector populated with at least half one’s. This gives an exponential separation between randomized query complexity and pseudo-deterministic complexity, which is tight in the quantum setting. As applications we partially solve a related combinatorial coloring problem, and we separate random tree-like Resolution from its pseudo-deterministic version. In contrast to our lower bound, we show, surprisingly, that in the zero-error, average case setting, the three notions (deterministic, randomized, pseudo-deterministic) collapse. |
| spellingShingle | Goldwasser, S Impagliazzo, R Pitassi, T Santhanam, R On the pseudo-deterministic query complexity of NP search problems |
| title | On the pseudo-deterministic query complexity of NP search problems |
| title_full | On the pseudo-deterministic query complexity of NP search problems |
| title_fullStr | On the pseudo-deterministic query complexity of NP search problems |
| title_full_unstemmed | On the pseudo-deterministic query complexity of NP search problems |
| title_short | On the pseudo-deterministic query complexity of NP search problems |
| title_sort | on the pseudo deterministic query complexity of np search problems |
| work_keys_str_mv | AT goldwassers onthepseudodeterministicquerycomplexityofnpsearchproblems AT impagliazzor onthepseudodeterministicquerycomplexityofnpsearchproblems AT pitassit onthepseudodeterministicquerycomplexityofnpsearchproblems AT santhanamr onthepseudodeterministicquerycomplexityofnpsearchproblems |