5 Search Results for "Witmer, David"

Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.13
Exploring the Symbiotic Collaboration Paradigm in Virtual Reality and Its Potential Applications to Human Spaceflight

Authors: Florian Dufresne, Geoffrey Gorisse, and Olivier Christmann

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
As the quest to go back to the Moon and beyond continues, preparation for such critical missions relies in part on the use of immersive technologies. Especially, Virtual Reality (VR) unique affordances allow to simulate scenarios in a convincing digitally recreated space. But the potential of VR is not limited to solely emulating real-world environments. Indeed, some works from the Human-Computer Interaction (HCI) community explored new ways to collaborate virtually by inhabiting the same virtual representation, namely an avatar. Taking this paradigm further, one could offer new ways to collaborate between an immersed VR user and an external supervisor being granted access to the virtual environment by way of non-immersive devices like a computer or a smartphone. The non-immersed user could for instance inhabit some body parts of the VR user’s avatar to benefit from unique viewpoints and leverage mutual spatial awareness, as well as social interactions, alike a symbiotic relationship that benefits both actors. Therefore, this paper introduces our on-going research project exploring this new paradigm of symbiotic co-embodiment as a tool leveraging social presence during supervised embodied sessions in VR. It especially discusses how this paradigm could benefit human spaceflight, both in mission preparation and during spaceflight.
Cite as

Florian Dufresne, Geoffrey Gorisse, and Olivier Christmann. Exploring the Symbiotic Collaboration Paradigm in Virtual Reality and Its Potential Applications to Human Spaceflight. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dufresne_et_al:OASIcs.SpaceCHI.2025.13,
  author =	{Dufresne, Florian and Gorisse, Geoffrey and Christmann, Olivier},
  title =	{{Exploring the Symbiotic Collaboration Paradigm in Virtual Reality and Its Potential Applications to Human Spaceflight}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{13:1--13:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.13},
  URN =		{urn:nbn:de:0030-drops-240034},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.13},
  annote =	{Keywords: Virtual Reality, Co-Embodiment, Human Spaceflight, Supervised Training, On-field Activities}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.17
Spectral Refutations of Semirandom k-LIN over Larger Fields

Authors: Nicholas Kocurek and Peter Manohar

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study the problem of strongly refuting semirandom k-LIN(𝔽) instances: systems of k-sparse inhomogeneous linear equations over a finite field 𝔽. For the case of 𝔽 = 𝔽₂, this is the well-studied problem of refuting semirandom instances of k-XOR, where the works of [Venkatesan Guruswami et al., 2022; Jun-Ting Hsieh et al., 2023] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter 𝓁, they give an n^{O(𝓁)}-time algorithm to certify that there is no assignment that can satisfy more than 1/2 + ε-fraction of constraints in a semirandom k-XOR instance, provided that the instance has O(n)⋅(n/𝓁)^{k/2 - 1} log n/ε⁴ constraints, and the work of [Pravesh K. Kothari et al., 2017] provides good evidence that this tight up to a polylog(n) factor via lower bounds for the Sum-of-Squares hierarchy. However, for larger fields, the only known results for this problem are established via black-box reductions to the case of 𝔽₂, resulting in a |𝔽|^{3k} gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom k-LIN(𝔽) instances with the "correct" dependence on the field size |𝔽|. For any choice of a parameter 𝓁, our algorithm runs in (|𝔽|)^O(𝓁)-time and strongly refutes semirandom k-LIN(𝔽) instances with at least O(n) ⋅ (|𝔽^*| n/𝓁) ^{k/2 - 1} log(n|𝔽^*|)/ε⁴ constraints. We give good evidence that this dependence on the field size |𝔽| is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a polylog(n |𝔽^*|) factor. Our results also extend beyond finite fields to the more general case of ℤ_m and arbitrary finite Abelian groups. Our key technical innovation is a generalization of the "𝔽₂ Kikuchi matrices" of [Alexander S. Wein et al., 2019; Venkatesan Guruswami et al., 2022] to larger fields, and finite Abelian groups more generally.
Cite as

Nicholas Kocurek and Peter Manohar. Spectral Refutations of Semirandom k-LIN over Larger Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kocurek_et_al:LIPIcs.APPROX/RANDOM.2025.17,
  author =	{Kocurek, Nicholas and Manohar, Peter},
  title =	{{Spectral Refutations of Semirandom k-LIN over Larger Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.17},
  URN =		{urn:nbn:de:0030-drops-243834},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.17},
  annote =	{Keywords: Spectral Algorithms, CSP Refutation, Kikuchi Matrices}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.32
A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion

Authors: Anastasia Sofronova and Dmitry Sokolov

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Random Δ-CNF formulas are one of the few candidates that are expected to be hard for proof systems and SAT algotirhms. Assume we sample m clauses over n variables. Here, the main complexity parameter is clause density, χ := m/n. For a fixed Δ, there exists a satisfiability threshold c_Δ such that for χ > c_Δ a formula is unsatisfiable with high probability. and for χ < c_Δ it is satisfiable with high probability. Near satisfiability threshold, there are various lower bounds for algorithms and proof systems [Eli Ben-Sasson, 2001; Eli Ben-Sasson and Russell Impagliazzo, 1999; Michael Alekhnovich and Alexander A. Razborov, 2003; Dima Grigoriev, 2001; Grant Schoenebeck, 2008; Pavel Hrubes and Pavel Pudlák, 2017; Noah Fleming et al., 2017; Dmitry Sokolov, 2024], and for high-density regimes, there exist upper bounds [Uriel Feige et al., 2006; Sebastian Müller and Iddo Tzameret, 2014; Jackson Abascal et al., 2021; Venkatesan Guruswami et al., 2022]. One of the frontiers in the direction of proving lower bounds on these formulas is the k-DNF Resolution proof system (aka Res(k)). There are several known results for k = 𝒪(√{log n}/{log log n}}) [Nathan Segerlind et al., 2004; Michael Alekhnovich, 2011], that are applicable only for density regime near the threshold. In this paper, we show the first Res(k) lower bound that is applicable in higher-density regimes. Our results work for slightly larger k = 𝒪(√{log n}).
Cite as

Anastasia Sofronova and Dmitry Sokolov. A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 32:1-32:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sofronova_et_al:LIPIcs.CCC.2025.32,
  author =	{Sofronova, Anastasia and Sokolov, Dmitry},
  title =	{{A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{32:1--32:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.32},
  URN =		{urn:nbn:de:0030-drops-237269},
  doi =		{10.4230/LIPIcs.CCC.2025.32},
  annote =	{Keywords: proof complexity, random CNFs}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.41
Lower Bounds for CSP Refutation by SDP Hierarchies

Authors: Ryuhei Mori and David Witmer

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
For a k-ary predicate P, a random instance of CSP(P) with n variables and m constraints is unsatisfiable with high probability when m >= O(n). The natural algorithmic task in this regime is refutation: finding a proof that a given random instance is unsatisfiable. Recent work of Allen et al. suggests that the difficulty of refuting CSP(P) using an SDP is determined by a parameter cmplx(P), the smallest t for which there does not exist a t-wise uniform distribution over satisfying assignments to P. In particular they show that random instances of CSP(P) with m >> n^{cmplx(P)/2} can be refuted efficiently using an SDP. In this work, we give evidence that n^{cmplx(P)/2} constraints are also necessary for refutation using SDPs. Specifically, we show that if P supports a (t-1)-wise uniform distribution over satisfying assignments, then the Sherali-Adams_+ and Lovasz-Schrijver_+ SDP hierarchies cannot refute a random instance of CSP(P) in polynomial time for any m <= n^{t/2-epsilon}.
Cite as

Ryuhei Mori and David Witmer. Lower Bounds for CSP Refutation by SDP Hierarchies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 41:1-41:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mori_et_al:LIPIcs.APPROX-RANDOM.2016.41,
  author =	{Mori, Ryuhei and Witmer, David},
  title =	{{Lower Bounds for CSP Refutation by SDP Hierarchies}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{41:1--41:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.41},
  URN =		{urn:nbn:de:0030-drops-66645},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.41},
  annote =	{Keywords: constraint satisfaction problems, LP and SDP relaxations, average-case complexity}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.110
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

Authors: Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.
Cite as

Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 110-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{barak_et_al:LIPIcs.APPROX-RANDOM.2015.110,
  author =	{Barak, Boaz and Moitra, Ankur and O’Donnell, Ryan and Raghavendra, Prasad and Regev, Oded and Steurer, David and Trevisan, Luca and Vijayaraghavan, Aravindan and Witmer, David and Wright, John},
  title =	{{Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{110--123},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.110},
  URN =		{urn:nbn:de:0030-drops-52981},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.110},
  annote =	{Keywords: constraint satisfaction problems, bounded degree, advantage over random}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2016
  • 1 2015

  • Refine by Author
  • 2 Witmer, David
  • 1 Barak, Boaz
  • 1 Christmann, Olivier
  • 1 Dufresne, Florian
  • 1 Gorisse, Geoffrey
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Human-centered computing → Collaborative interaction
  • 1 Human-centered computing → Virtual reality
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 2 constraint satisfaction problems
  • 1 CSP Refutation
  • 1 Co-Embodiment
  • 1 Human Spaceflight
  • 1 Kikuchi Matrices
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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