On the average-case hardness of total search problems
Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.
Download
Thesis
| PhD
| Published
| English
Author
Supervisor
Department
Series Title
ISTA Thesis
Abstract
A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems
like computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.
Almost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.
However, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic
problem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.
Our main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions.
Publishing Year
Date Published
2020-05-25
Publisher
Institute of Science and Technology Austria
Page
126
ISSN
IST-REx-ID
Cite this
Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:10.15479/AT:ISTA:7896
Kamath Hosdurg, C. (2020). On the average-case hardness of total search problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896
Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.
C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.
Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.
Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2020_Thesis_Kamath.pdf
1.62 MB
Access Level
Open Access
Date Uploaded
2020-05-26
MD5 Checksum
b39e2e1c376f5819b823fb7077491c64
Source File
File Name
Thesis_Kamath.zip
15.30 MB
Access Level
Closed Access
Date Uploaded
2020-05-26
MD5 Checksum
8b26ba729c1a85ac6bea775f5d73cdc7
Material in ISTA:
Part of this Dissertation