3 Search Results for "Raz, Gal"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.35
Fooling Near-Maximal Decision Trees

Authors: William M. Hoza and Zelin Lv

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

Abstract
For any constant α > 0, we construct an explicit pseudorandom generator (PRG) that fools n-variate decision trees of size m with error ε and seed length (1 + α) ⋅ log₂ m + O(log(1/ε) + log log n). For context, one can achieve seed length (2 + o(1)) ⋅ log₂ m + O(log(1/ε) + log log n) using well-known constructions and analyses of small-bias distributions, but such a seed length is trivial when m ≥ 2^{n/2}. Our approach is to develop a new variant of the classic concept of almost k-wise independence, which might be of independent interest. We say that a distribution X over {0, 1}ⁿ is k-wise ε-probably uniform if every Boolean function f that depends on only k variables satisfies 𝔼[f(X)] ≥ (1 - ε) ⋅ 𝔼[f]. We show how to sample a k-wise ε-probably uniform distribution using a seed of length (1 + α) ⋅ k + O(log(1/ε) + log log n). Meanwhile, we also show how to construct a set H ⊆ 𝔽₂ⁿ such that every feasible system of k linear equations in n variables over 𝔽₂ has a solution in H. The cardinality of H and the time complexity of enumerating H are at most 2^{k + o(k) + polylog n}, whereas small-bias distributions would give a bound of 2^{2k + O(log(n/k))}. By combining our new constructions with work by Chen and Kabanets (TCS 2016), we obtain nontrivial PRGs and hitting sets for linear-size Boolean circuits. Specifically, we get an explicit PRG with seed length (1 - Ω(1)) ⋅ n that fools circuits of size 2.99 ⋅ n over the U₂ basis, and we get a hitting set with time complexity 2^{(1 - Ω(1)) ⋅ n} for circuits of size 2.49 ⋅ n over the B₂ basis.
Cite as

William M. Hoza and Zelin Lv. Fooling Near-Maximal Decision Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.35,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{Fooling Near-Maximal Decision Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{35:1--35:24},
  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.35},
  URN =		{urn:nbn:de:0030-drops-244019},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.35},
  annote =	{Keywords: almost k-wise independence, decision trees, pseudorandom generators}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.68
New Pseudorandom Generators and Correlation Bounds Using Extractors

Authors: Vinayak M. Kumar

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

Abstract
We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalization of structured low-degree 𝔽₂-polynomials that we did not have correlation bounds for before. In particular: - We construct a PRG for width-2 poly(n)-length branching programs which read d bits at a time with seed length 2^O(√{log n}) ⋅ d²log²(1/ε). This comes quadratically close to optimal dependence in d and log(1/ε). Improving the dependence on n would imply nontrivial PRGs for log n-degree 𝔽₂-polynomials. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on d with seed length of O(dlog n + d2^dlog(1/ε)). - We provide the first nontrivial (and nearly optimal) correlation bounds and PRGs against size-n^Ω(log n) AC⁰ circuits with either n^{.99} SYM gates (computing an arbitrary symmetric function) or n^{.49} THR gates (computing an arbitrary linear threshold function). This is a generalization of sparse 𝔽₂-polynomials, which can be simulated by an AC⁰ circuit with one parity gate at the top. Previous work of Servedio and Tan only handled n^{.49} SYM gates or n^{.24} THR gates, and previous work of Lovett and Srinivasan only handled polynomial-size circuits. - We give exponentially small correlation bounds against degree-n^O(1) 𝔽₂-polynomials which are set-multilinear over some arbitrary partition of the input into n^{1-O(1)} parts (noting that at n parts, we recover all low degree polynomials). This vastly generalizes correlation bounds against degree-d polynomials which are set-multilinear over a fixed partition into d blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty, and Kumar. The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds for more general models of computation. Although this technique has been used in previous work, they rely on the model simplifying drastically under random restrictions. We view our results as a proof of concept that such fortification can be done even for classes that do not enjoy such behavior.
Cite as

Vinayak M. Kumar. New Pseudorandom Generators and Correlation Bounds Using Extractors. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 68:1-68:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumar:LIPIcs.ITCS.2025.68,
  author =	{Kumar, Vinayak M.},
  title =	{{New Pseudorandom Generators and Correlation Bounds Using Extractors}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{68:1--68:23},
  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.68},
  URN =		{urn:nbn:de:0030-drops-226961},
  doi =		{10.4230/LIPIcs.ITCS.2025.68},
  annote =	{Keywords: Pseudorandom Generators, Correlation Bounds, Constant-Depth Circuits}
}
Document
DOI: 10.4230/OASIcs.CMN.2014.42
Towards Empathic Neurofeedback for Interactive Storytelling

Authors: Marc Cavazza, Gabor Aranyi, Fred Charles, Julie Porteous, Stephen Gilroy, Ilana Klovatch, Gilan Jackont, Eyal Soreq, Nimrod Jakob Keynan, Avihay Cohen, Gal Raz, and Talma Hendler

Published in: OASIcs, Volume 41, 2014 Workshop on Computational Models of Narrative

Abstract
Interactive Narrative is a form of digital entertainment based on AI techniques which support narrative generation and user interaction. Despite recent progress in the field, there is still a lack of unified models integrating narrative generation, user response and interaction. This paper addresses this issue by revisiting existing Interactive Narrative paradigms, granting explicit status to users' disposition towards story characters. We introduce a novel Brain-Computer Interface (BCI) design, which attempts to capture empathy for the main character in a way that is compatible with filmic theories of emotion. Results from two experimental studies with a fully-implemented system demonstrate the effectiveness of a neurofeedback-based approach, showing that subjects can successfully modulate their emotional support for a character who is confronted with challenging situations. A preliminary fMRI analysis also shows activation during user interaction, in regions of the brain associated with emotional control.
Cite as

Marc Cavazza, Gabor Aranyi, Fred Charles, Julie Porteous, Stephen Gilroy, Ilana Klovatch, Gilan Jackont, Eyal Soreq, Nimrod Jakob Keynan, Avihay Cohen, Gal Raz, and Talma Hendler. Towards Empathic Neurofeedback for Interactive Storytelling. In 2014 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 41, pp. 42-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cavazza_et_al:OASIcs.CMN.2014.42,
  author =	{Cavazza, Marc and Aranyi, Gabor and Charles, Fred and Porteous, Julie and Gilroy, Stephen and Klovatch, Ilana and Jackont, Gilan and Soreq, Eyal and Keynan, Nimrod Jakob and Cohen, Avihay and Raz, Gal and Hendler, Talma},
  title =	{{Towards Empathic Neurofeedback for Interactive Storytelling}},
  booktitle =	{2014 Workshop on Computational Models of Narrative},
  pages =	{42--60},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-71-2},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{41},
  editor =	{Finlayson, Mark A. and Meister, Jan Christoph and Bruneau, Emile G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2014.42},
  URN =		{urn:nbn:de:0030-drops-46442},
  doi =		{10.4230/OASIcs.CMN.2014.42},
  annote =	{Keywords: brain-computer interfaces, neurofeedback, interactive narrative, affective computing}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2014

  • Refine by Author
  • 1 Aranyi, Gabor
  • 1 Cavazza, Marc
  • 1 Charles, Fred
  • 1 Cohen, Avihay
  • 1 Gilroy, Stephen
  • Show More...

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

  • Refine by Classification
  • 2 Theory of computation → Pseudorandomness and derandomization
  • 1 Theory of computation → Circuit complexity

  • Refine by Keyword
  • 1 Constant-Depth Circuits
  • 1 Correlation Bounds
  • 1 Pseudorandom Generators
  • 1 affective computing
  • 1 almost k-wise independence
  • 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