Zobrazeno 1 - 10
of 46
pro vyhledávání: '"Rahul Santhanam"'
Publikováno v:
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS).
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3bc4f45a0361bf205582ef90b8b029fb
https://doi.org/10.1109/focs54457.2022.00067
https://doi.org/10.1109/focs54457.2022.00067
Publikováno v:
Theory of Computing. 17:1-38
This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.W
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e473bfd8b58fae61db8ad408d99651a2
https://doi.org/10.4086/toc.2021.v017a011
https://doi.org/10.4086/toc.2021.v017a011
Publikováno v:
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e491b296ab67f79e9a0414b76727fa4f
https://doi.org/10.1145/3519935.3520051
https://doi.org/10.1145/3519935.3520051
For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions:
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::70cf6367f1b6313051d4dee104fc8553
http://arxiv.org/abs/2203.14379
http://arxiv.org/abs/2203.14379
Autor:
Rahul Santhanam
Publikováno v:
SSRN Electronic Journal.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::58a24659465738d459b1c33c1a3eff2c
https://doi.org/10.2139/ssrn.4219399
https://doi.org/10.2139/ssrn.4219399
Publikováno v:
STOC
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of BPTIME: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follow
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::28ae2ce8988db8dbf4796694465a8d2a
http://wrap.warwick.ac.uk/152052/7/WRAP-Pseudodeterministic-algorithms-structure-probabilistic-time-2021.pdf
http://wrap.warwick.ac.uk/152052/7/WRAP-Pseudodeterministic-algorithms-structure-probabilistic-time-2021.pdf
Autor:
Rahul Santhanam, Iddo Tzameret
Publikováno v:
STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing
STOC
STOC
We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally. We use the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba2b60f5bf67834dcb9a66d5623746d4
http://hdl.handle.net/10044/1/93966
http://hdl.handle.net/10044/1/93966
Autor:
Ján Pich, Rahul Santhanam
Publikováno v:
STOC
We show unconditionally that Cook’s theory PV formalizing poly-time reasoning cannot prove, for any non-deterministic poly-time machine M defining a language L(M), that L(M) is inapproximable by co-nondeterministic circuits of sub-exponential size.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce1e3f3a3e3998398a88fc1a75ceea24
https://doi.org/10.1145/3406325.3451117
https://doi.org/10.1145/3406325.3451117
Autor:
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Hardness magnification reduces major complexity separations (such as EXP ⊈ NC 1 ) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [ 11 , 13 , 14 , 40 , 42 , 43 , 46 ] have established results of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fcbd51fd8e7c238ae8d9fd7c6e9358ce
Publikováno v:
Theory of Computing. 14:1-55
$ \newcommand{\cclass}[1]{\normalfont\textsf{##1}} $We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer $d > 1$, there is a consta
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::80b2d4d8af9be537532b8171be4c434a
https://doi.org/10.4086/toc.2018.v014a009
https://doi.org/10.4086/toc.2018.v014a009