3 Search Results for "Ribeiro, David"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.10
Low-Degree Polynomials Extract From Local Sources

Authors: Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem.
Cite as

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.ICALP.2022.10,
  author =	{Alrabiah, Omar and Chattopadhyay, Eshan and Goodman, Jesse and Li, Xin and Ribeiro, Jo\~{a}o},
  title =	{{Low-Degree Polynomials Extract From Local Sources}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.10},
  URN =		{urn:nbn:de:0030-drops-163519},
  doi =		{10.4230/LIPIcs.ICALP.2022.10},
  annote =	{Keywords: Randomness extractors, local sources, samplable sources, AC⁰ circuits, branching programs, low-degree polynomials, Chevalley-Warning}
}
Document
DOI: 10.4230/OASIcs.LDK.2021.15
Enriching Word Embeddings with Food Knowledge for Ingredient Retrieval

Authors: Álvaro Mendes Samagaio, Henrique Lopes Cardoso, and David Ribeiro

Published in: OASIcs, Volume 93, 3rd Conference on Language, Data and Knowledge (LDK 2021)

Abstract
Smart assistants and recommender systems must deal with lots of information coming from different sources and having different formats. This is more frequent in text data, which presents increased variability and complexity, and is rather common for conversational assistants or chatbots. Moreover, this issue is very evident in the food and nutrition lexicon, where the semantics present increased variability, namely due to hypernyms and hyponyms. This work describes the creation of a set of word embeddings based on the incorporation of information from a food thesaurus - LanguaL - through retrofitting. The ingredients were classified according to three different facet label groups. Retrofitted embeddings seem to properly encode food-specific knowledge, as shown by an increase on accuracy as compared to generic embeddings (+23%, +10% and +31% per group). Moreover, a weighing mechanism based on TF-IDF was applied to embedding creation before retrofitting, also bringing an increase on accuracy (+5%, +9% and +5% per group). Finally, the approach has been tested with human users in an ingredient retrieval exercise, showing very positive evaluation (77.3% of the volunteer testers preferred this method over a string-based matching algorithm).
Cite as

Álvaro Mendes Samagaio, Henrique Lopes Cardoso, and David Ribeiro. Enriching Word Embeddings with Food Knowledge for Ingredient Retrieval. In 3rd Conference on Language, Data and Knowledge (LDK 2021). Open Access Series in Informatics (OASIcs), Volume 93, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{samagaio_et_al:OASIcs.LDK.2021.15,
  author =	{Samagaio, \'{A}lvaro Mendes and Lopes Cardoso, Henrique and Ribeiro, David},
  title =	{{Enriching Word Embeddings with Food Knowledge for Ingredient Retrieval}},
  booktitle =	{3rd Conference on Language, Data and Knowledge (LDK 2021)},
  pages =	{15:1--15:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-199-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{93},
  editor =	{Gromann, Dagmar and S\'{e}rasset, Gilles and Declerck, Thierry and McCrae, John P. and Gracia, Jorge and Bosque-Gil, Julia and Bobillo, Fernando and Heinisch, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.LDK.2021.15},
  URN =		{urn:nbn:de:0030-drops-145510},
  doi =		{10.4230/OASIcs.LDK.2021.15},
  annote =	{Keywords: Word embeddings, Retrofitting, LanguaL, Food Embeddings, Knowledge Graph}
}
Document
DOI: 10.4230/DagSemProc.07311.6
CodeVoting: protecting against malicious vote manipulation at the voter's PC

Authors: Rui Joaquim and Carlos Ribeiro

Published in: Dagstuhl Seminar Proceedings, Volume 7311, Frontiers of Electronic Voting (2008)

Abstract
Voting in uncontrolled environments, such as the Internet comes with a price, the price of having to trust in uncontrolled machines the collection of voter's vote. An uncontrolled machine, e.g. the voter's PC, may be infected with a virus or other malicious program that may try to change the voter's vote without her knowledge. Here we present CodeVoting, a technique to create a secure communication channel to a smart card that prevents vote manipulation by the voter's PC, while at the same time allows the use of any cryptographic voting protocol to cast the vote.
Cite as

Rui Joaquim and Carlos Ribeiro. CodeVoting: protecting against malicious vote manipulation at the voter's PC. In Frontiers of Electronic Voting. Dagstuhl Seminar Proceedings, Volume 7311, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{joaquim_et_al:DagSemProc.07311.6,
  author =	{Joaquim, Rui and Ribeiro, Carlos},
  title =	{{CodeVoting: protecting against malicious vote manipulation at the voter's PC}},
  booktitle =	{Frontiers of Electronic Voting},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7311},
  editor =	{David Chaum and Miroslaw Kutylowski and Ronald L. Rivest and Peter Y. A. Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07311.6},
  URN =		{urn:nbn:de:0030-drops-12997},
  doi =		{10.4230/DagSemProc.07311.6},
  annote =	{Keywords: Internet voting, vote manipulation}
}
  • Refine by Author
  • 1 Alrabiah, Omar
  • 1 Chattopadhyay, Eshan
  • 1 Goodman, Jesse
  • 1 Joaquim, Rui
  • 1 Li, Xin
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Artificial intelligence
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Computing methodologies → Lexical semantics
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 AC⁰ circuits
  • 1 Chevalley-Warning
  • 1 Food Embeddings
  • 1 Internet voting
  • 1 Knowledge Graph
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2021
  • 1 2022

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