2 Search Results for "Williams, Ian"

Document
DOI: 10.4230/LIPIcs.CCC.2023.6
Bounded Relativization

Authors: Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called bounded relativization. For a complexity class ℭ, we say that a statement is ℭ-relativizing if the statement holds relative to every oracle 𝒪 ∈ ℭ. It is easy to see that every result that relativizes also ℭ-relativizes for every complexity class ℭ. On the other hand, we observe that many non-relativizing results, such as IP = PSPACE, are in fact PSPACE-relativizing. First, we use the idea of bounded relativization to obtain new lower bound results, including the following nearly maximum circuit lower bound: for every constant ε > 0, BPE^{MCSP}/2^{εn} ⊈ SIZE[2ⁿ/n]. We prove this by PSPACE-relativizing the recent pseudodeterministic pseudorandom generator by Lu, Oliveira, and Santhanam (STOC 2021). Next, we study the limitations of PSPACE-relativizing proof techniques, and show that a seemingly minor improvement over the known results using PSPACE-relativizing techniques would imply a breakthrough separation NP ≠ L. For example: - Impagliazzo and Wigderson (JCSS 2001) proved that if EXP ≠ BPP, then BPP admits infinitely-often subexponential-time heuristic derandomization. We show that their result is PSPACE-relativizing, and that improving it to worst-case derandomization using PSPACE-relativizing techniques implies NP ≠ L. - Oliveira and Santhanam (STOC 2017) recently proved that every dense subset in P admits an infinitely-often subexponential-time pseudodeterministic construction, which we observe is PSPACE-relativizing. Improving this to almost-everywhere (pseudodeterministic) or (infinitely-often) deterministic constructions by PSPACE-relativizing techniques implies NP ≠ L. - Santhanam (SICOMP 2009) proved that pr-MA does not have fixed polynomial-size circuits. This lower bound can be shown PSPACE-relativizing, and we show that improving it to an almost-everywhere lower bound using PSPACE-relativizing techniques implies NP ≠ L. In fact, we show that if we can use PSPACE-relativizing techniques to obtain the above-mentioned improvements, then PSPACE ≠ EXPH. We obtain our barrier results by constructing suitable oracles computable in EXPH relative to which these improvements are impossible.
Cite as

Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 6:1-6:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.CCC.2023.6,
  author =	{Hirahara, Shuichi and Lu, Zhenjian and Ren, Hanlin},
  title =	{{Bounded Relativization}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{6:1--6:45},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.6},
  URN =		{urn:nbn:de:0030-drops-182764},
  doi =		{10.4230/LIPIcs.CCC.2023.6},
  annote =	{Keywords: relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs}
}
Document
DOI: 10.4230/DagRep.12.1.83
Privacy Protection of Automated and Self-Driving Vehicles (Dagstuhl Seminar 22042)

Authors: Frank Kargl, Ioannis Krontiris, André Weimerskirch, Ian Williams, and Nataša Trkulja

Published in: Dagstuhl Reports, Volume 12, Issue 1 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22042 "Privacy Protection of Automated and Self-Driving Vehicles". The Seminar reviewed existing privacy-enhancing technologies, standards, tools, and frameworks for protecting personal information in the context of automated and self-driving vehicles (AVs). We specifically focused on where such existing techniques clash with requirements of an AV and its data processing and identified the major road blockers on the way to deployment of privacy protection in AVs from a legal, technical, business and ethical perspective. Therefore, the seminar took an interdisciplinary approach involving autonomous and connected driving, privacy protection, and legal data protection experts. This report summarizes the discussions and findings during the seminar, includes the abstracts of talks, and includes a report from the working groups.
Cite as

Frank Kargl, Ioannis Krontiris, André Weimerskirch, Ian Williams, and Nataša Trkulja. Privacy Protection of Automated and Self-Driving Vehicles (Dagstuhl Seminar 22042). In Dagstuhl Reports, Volume 12, Issue 1, pp. 83-100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{kargl_et_al:DagRep.12.1.83,
  author =	{Kargl, Frank and Krontiris, Ioannis and Weimerskirch, Andr\'{e} and Williams, Ian and Trkulja, Nata\v{s}a},
  title =	{{Privacy Protection of Automated and Self-Driving Vehicles (Dagstuhl Seminar 22042)}},
  pages =	{83--100},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{1},
  editor =	{Kargl, Frank and Krontiris, Ioannis and Weimerskirch, Andr\'{e} and Williams, Ian and Trkulja, Nata\v{s}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.1.83},
  URN =		{urn:nbn:de:0030-drops-169220},
  doi =		{10.4230/DagRep.12.1.83},
  annote =	{Keywords: automotive security and privacy, privacy and data protection}
}
  • Refine by Author
  • 1 Hirahara, Shuichi
  • 1 Kargl, Frank
  • 1 Krontiris, Ioannis
  • 1 Lu, Zhenjian
  • 1 Ren, Hanlin
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Human and societal aspects of security and privacy
  • 1 Security and privacy → Privacy protections
  • 1 Security and privacy → Privacy-preserving protocols
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 1 automotive security and privacy
  • 1 circuit lower bound
  • 1 derandomization
  • 1 explicit construction
  • 1 interactive proofs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact