Master’s Thesis Presentation • Algorithms and Complexity • Variants of Pseudo-deterministic Algorithms and Duality in TFNPExport this event to calendar

Thursday, August 3, 2023 — 9:30 AM to 10:30 AM EDT

Please note: This master’s thesis presentation will take place in DC 3317 and online.

Mohammad Hossein Ebtehaj, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Shalev Ben-David

We introduce a new notion of “faux-deterministic” algorithms for search problems in query complexity. Roughly, for a search problem $\cS$, a faux-deterministic algorithm is a probability distribution $\mathcal{A}$ over deterministic algorithms such that no computationally bounded adversary making black-box query to an algorithm $A\sim \mathcal{A}$ can find an input on which it fails to solve $\cS$. Faux-deterministic algorithms are a relaxation of pseudo-deterministic algorithms, which are randomized algorithms with the guarantee that for any given input $x$, the algorithm outputs a unique output $y_x$ with high probability.

Pseudo-deterministic algorithms are statistically indistinguishable from deterministic algorithms, while faux-deterministic algorithms relax the statistical indistinguishability to computational indistinguishability.

We prove that in the query model, every verifiable search problem with a randomized algorithm also has a faux-deterministic algorithm. This immediately proves an exponential gap between pseudo-deterministic and faux-deterministic complexities in query complexity. We additionally show that our faux-deterministic algorithm is also secure against quantum adversaries that can make black-box queries in superposition.

We highlight two reasons to study faux-deterministic algorithms. First, for practical purposes, one can use a faux-deterministic algorithm instead of pseudo-deterministic algorithms in most cases where the latter is required. Second, since efficient faux-deterministic algorithms exist even when pseudo-deterministic ones do not, their existence demonstrates a barrier for proving pseudo-deterministic lower bounds: lower bounds on pseudo-determinism must distinguish pseudo-determinism from faux-determinism.

Finally, changing our perspective to adversaries’ viewpoint, we introduce the notion of a dual problem for search problems $\cS$. In the dual problem $\cS^*$, the input is an algorithm $A$ purporting to solve $\cS$, and our goal is to find an adverse input $x$ on which $A$ fails to solve $\cS$. We discuss several properties in the query and Turing machine model that show the new problem $\cS^*$ is analogous to a dual for $\cS$.


To attend this master’s thesis presentation in person, please go to DC 3317. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/my/mhebtehaj.

Location 
DC - William G. Davis Computer Research Centre
Hybrid: DC 3317 | Online master’s thesis presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
  1. 2024 (186)
    1. September (1)
    2. August (6)
    3. July (21)
    4. June (17)
    5. May (23)
    6. April (41)
    7. March (27)
    8. February (25)
    9. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)