Search Results

Documents authored by Lecomte, Victor

Document
DOI: 10.4230/LIPIcs.ITCS.2025.38
Backdoor Defense, Learnability and Obfuscation

Authors: Paul Christiano, Jacob Hilton, Victor Lecomte, and Mark Xu

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We introduce a formal notion of defendability against backdoors using a game between an attacker and a defender. In this game, the attacker modifies a function to behave differently on a particular input known as the "trigger", while behaving the same almost everywhere else. The defender then attempts to detect the trigger at evaluation time. If the defender succeeds with high enough probability, then the function class is said to be defendable. The key constraint on the attacker that makes defense possible is that the attacker’s strategy must work for a randomly-chosen trigger. Our definition is simple and does not explicitly mention learning, yet we demonstrate that it is closely connected to learnability. In the computationally unbounded setting, we use a voting algorithm of [Hanneke et al., 2022] to show that defendability is essentially determined by the VC dimension of the function class, in much the same way as PAC learnability. In the computationally bounded setting, we use a similar argument to show that efficient PAC learnability implies efficient defendability, but not conversely. On the other hand, we use indistinguishability obfuscation to show that the class of polynomial size circuits is not efficiently defendable. Finally, we present polynomial size decision trees as a natural example for which defense is strictly easier than learning. Thus, we identify efficient defendability as a notable intermediate concept in between efficient learnability and obfuscation.
Cite as

Paul Christiano, Jacob Hilton, Victor Lecomte, and Mark Xu. Backdoor Defense, Learnability and Obfuscation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{christiano_et_al:LIPIcs.ITCS.2025.38,
  author =	{Christiano, Paul and Hilton, Jacob and Lecomte, Victor and Xu, Mark},
  title =	{{Backdoor Defense, Learnability and Obfuscation}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{38:1--38:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.38},
  URN =		{urn:nbn:de:0030-drops-226662},
  doi =		{10.4230/LIPIcs.ITCS.2025.38},
  annote =	{Keywords: backdoors, machine learning, PAC learning, indistinguishability obfuscation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.42
Hardness Amplification for Dynamic Binary Search Trees

Authors: Shunhua Jiang, Victor Lecomte, Omri Weinstein, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We prove direct-sum theorems for Wilber’s two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the question of dynamic optimality [Sleator and Tarjan, JACM'85]: the Alternation bound is the only bound to have yielded online BST algorithms beating log n competitive ratio, while the Funnel bound has repeatedly been conjectured to exactly characterize the cost of executing an access sequence using the optimal tree [Wilber, FOCS'86, Kozma'16], and has been explicitly linked to splay trees [Levy and Tarjan, SODA'19]. Previously, the direct-sum theorem for the Alternation bound was known only when approximation was allowed [Chalermsook, Chuzhoy and Saranurak, APPROX'20, ToC'24]. We use these direct-sum theorems to amplify the sequences from [Lecomte and Weinstein, ESA'20] that separate between Wilber’s Alternation and Funnel bounds, increasing the Alternation and Funnel bounds while optimally maintaining the separation. As a corollary, we show that Tango trees [Demaine et al., FOCS'04] are optimal among any BST algorithms that charge their costs to the Alternation bound. This is true for any value of the Alternation bound, even values for which Tango trees achieve a competitive ratio of o(log log n) instead of the default O(log log n). Previously, the optimality of Tango trees was shown only for a limited range of Alternation bound [Lecomte and Weinstein, ESA'20].
Cite as

Shunhua Jiang, Victor Lecomte, Omri Weinstein, and Sorrachai Yingchareonthawornchai. Hardness Amplification for Dynamic Binary Search Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ISAAC.2024.42,
  author =	{Jiang, Shunhua and Lecomte, Victor and Weinstein, Omri and Yingchareonthawornchai, Sorrachai},
  title =	{{Hardness Amplification for Dynamic Binary Search Trees}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.42},
  URN =		{urn:nbn:de:0030-drops-221696},
  doi =		{10.4230/LIPIcs.ISAAC.2024.42},
  annote =	{Keywords: Data Structures, Amortized Analysis}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.19
The Composition Complexity of Majority

Authors: Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
We study the complexity of computing majority as a composition of local functions: Maj_n = h(g_1,…,g_m), where each g_j: {0,1}ⁿ → {0,1} is an arbitrary function that queries only k ≪ n variables and h: {0,1}^m → {0,1} is an arbitrary combining function. We prove an optimal lower bound of m ≥ Ω(n/k log k) on the number of functions needed, which is a factor Ω(log k) larger than the ideal m = n/k. We call this factor the composition overhead; previously, no superconstant lower bounds on it were known for majority. Our lower bound recovers, as a corollary and via an entirely different proof, the best known lower bound for bounded-width branching programs for majority (Alon and Maass '86, Babai et al. '90). It is also the first step in a plan that we propose for breaking a longstanding barrier in lower bounds for small-depth boolean circuits. Novel aspects of our proof include sharp bounds on the information lost as computation flows through the inner functions g_j, and the bootstrapping of lower bounds for a multi-output function (Hamming weight) into lower bounds for a single-output one (majority).
Cite as

Victor Lecomte, Prasanna Ramakrishnan, and Li-Yang Tan. The Composition Complexity of Majority. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 19:1-19:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lecomte_et_al:LIPIcs.CCC.2022.19,
  author =	{Lecomte, Victor and Ramakrishnan, Prasanna and Tan, Li-Yang},
  title =	{{The Composition Complexity of Majority}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{19:1--19:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.19},
  URN =		{urn:nbn:de:0030-drops-165818},
  doi =		{10.4230/LIPIcs.CCC.2022.19},
  annote =	{Keywords: computational complexity, circuit lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.68
Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality

Authors: Victor Lecomte and Omri Weinstein

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence X ∈ [n]^m. Both bounds play a central role in the ongoing pursuit of the dynamic optimality conjecture (Sleator and Tarjan, 1985), but their relationship remained unknown for more than three decades. We show that Wilber’s Funnel bound dominates his Alternation bound for all X, and give a tight Θ(lg lg n) separation for some X, answering Wilber’s conjecture and an open problem of Iacono, Demaine et. al. The main ingredient of the proof is a new symmetric characterization of Wilber’s Funnel bound, which proves that it is invariant under rotations of X. We use this characterization to provide initial indication that the Funnel bound matches the Independent Rectangle bound (Demaine et al., 2009), by proving that when the Funnel bound is constant, IRB_upRect is linear. To the best of our knowledge, our results provide the first progress on Wilber’s conjecture that the Funnel bound is dynamically optimal (1986).
Cite as

Victor Lecomte and Omri Weinstein. Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 68:1-68:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lecomte_et_al:LIPIcs.ESA.2020.68,
  author =	{Lecomte, Victor and Weinstein, Omri},
  title =	{{Settling the Relationship Between Wilber’s Bounds for Dynamic Optimality}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{68:1--68:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.68},
  URN =		{urn:nbn:de:0030-drops-129342},
  doi =		{10.4230/LIPIcs.ESA.2020.68},
  annote =	{Keywords: data structures, binary search trees, dynamic optimality, lower bounds}
}
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 About DROPS Imprint Privacy Contact