3 Search Results for "Reed, Chris"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.37
Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes

Authors: Huck Bennett and Chris Peikert

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

Abstract
We give a simple proof that the (approximate, decisional) Shortest Vector Problem is NP-hard under a randomized reduction. Specifically, we show that for any p ≥ 1 and any constant γ < 2^{1/p}, the γ-approximate problem in the 𝓁_p norm (γ-GapSVP_p) is not in RP unless NP ⊆ RP. Our proof follows an approach pioneered by Ajtai (STOC 1998), and strengthened by Micciancio (FOCS 1998 and SICOMP 2000), for showing hardness of γ-GapSVP_p using locally dense lattices. We construct such lattices simply by applying "Construction A" to Reed-Solomon codes with suitable parameters, and prove their local density via an elementary argument originally used in the context of Craig lattices. As in all known NP-hardness results for GapSVP_p with p < ∞, our reduction uses randomness. Indeed, it is a notorious open problem to prove NP-hardness via a deterministic reduction. To this end, we additionally discuss potential directions and associated challenges for derandomizing our reduction. In particular, we show that a close deterministic analogue of our local density construction would improve on the state-of-the-art explicit Reed-Solomon list-decoding lower bounds of Guruswami and Rudra (STOC 2005 and IEEE Transactions on Information Theory 2006). As a related contribution of independent interest, we also give a polynomial-time algorithm for decoding n-dimensional "Construction A Reed-Solomon lattices" (with different parameters than those used in our hardness proof) to a distance within an O(√log n) factor of Minkowski’s bound. This asymptotically matches the best known distance for decoding near Minkowski’s bound, due to Mook and Peikert (IEEE Transactions on Information Theory 2022), whose work we build on with a somewhat simpler construction and analysis.
Cite as

Huck Bennett and Chris Peikert. Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bennett_et_al:LIPIcs.APPROX/RANDOM.2023.37,
  author =	{Bennett, Huck and Peikert, Chris},
  title =	{{Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.37},
  URN =		{urn:nbn:de:0030-drops-188622},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.37},
  annote =	{Keywords: Lattices, Shortest Vector Problem, Reed-Solomon codes, NP-hardness, derandomization}
}
Document
DOI: 10.4230/DagRep.12.3.117
Framing in Communication: From Theories to Computation (Dagstuhl Seminar 22131)

Authors: Katarzyna Budzynska, Chris Reed, Manfred Stede, Benno Stein, and Zhang He

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

Abstract
Framing has become recognised as a powerful communication strategy for winning debates and shaping opinions and decisions. Entman defines framing as an action of selecting "some aspects of a perceived reality and make them more salient in a communicating text, in such a way as to promote a particular problem definition, causal interpretation, moral evaluation, and/or treatment recommendation for the item described". Instead of engaging in costly and difficult exchanges of argument and counter-argument, a politician or a journalist can then try to reframe a dialogue on, for example, fracking from economic benefits to environmental hazards, or a dialogue on abortion from pro-life to pro-choice. Introduced in 1960’s sociology, framing has been imported into communication sciences and media studies as an attempt to address the ways in which news is reported and, thus, a way in which to tackle manipulation and fake news. The topic has spread to other disciplines such as psychology, philosophy, semantics, pragmatics, political science, journalism, and, most recently – to computational linguistics and artificial intelligence. This seminar aims to pave the way to synthesising definitions developed in these theoretically and empirically driven areas and then to operationalise them in computational and applied areas by means of cross-disciplinary hands-on exchanges in facilitated discussions. Our goal is to support the development of innovative technologies, which can help us to quantify framing phenomena, to study framing at scale, and to deploy computational techniques in order to intervene against malicious attempts to influence opinions and decisions of the general public.
Cite as

Katarzyna Budzynska, Chris Reed, Manfred Stede, Benno Stein, and Zhang He. Framing in Communication: From Theories to Computation (Dagstuhl Seminar 22131). In Dagstuhl Reports, Volume 12, Issue 3, pp. 117-140, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{budzynska_et_al:DagRep.12.3.117,
  author =	{Budzynska, Katarzyna and Reed, Chris and Stede, Manfred and Stein, Benno and He, Zhang},
  title =	{{Framing in Communication: From Theories to Computation (Dagstuhl Seminar 22131)}},
  pages =	{117--140},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{3},
  editor =	{Budzynska, Katarzyna and Reed, Chris and Stede, Manfred and Stein, Benno and He, Zhang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.3.117},
  URN =		{urn:nbn:de:0030-drops-172713},
  doi =		{10.4230/DagRep.12.3.117},
  annote =	{Keywords: Communication Strategies, Discourse and Dialogue, Computational Argumentation, Natural Language Processing}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.23
On Higher-Order Fourier Analysis over Non-Prime Fields

Authors: Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta

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

Abstract
The celebrated Weil bound for character sums says that for any low-degree polynomial P and any additive character chi, either chi(P) is a constant function or it is distributed close to uniform. The goal of higher-order Fourier analysis is to understand the connection between the algebraic and analytic properties of polynomials (and functions, generally) at a more detailed level. For instance, what is the tradeoff between the equidistribution of chi(P) and its "structure"? Previously, most of the work in this area was over fields of prime order. We extend the tools of higher-order Fourier analysis to analyze functions over general finite fields. Let K be a field extension of a prime finite field F_p. Our technical results are: 1. If P: K^n -> K is a polynomial of degree <= d, and E[chi(P(x))] > |K|^{-s} for some s > 0 and non-trivial additive character chi, then P is a function of O_{d, s}(1) many non-classical polynomials of weight degree < d. The definition of non-classical polynomials over non-prime fields is one of the contributions of this work. 2. Suppose K and F are of bounded order, and let H be an affine subspace of K^n. Then, if P: K^n -> K is a polynomial of degree d that is sufficiently regular, then (P(x): x in H) is distributed almost as uniformly as possible subject to constraints imposed by the degree of P. Such a theorem was previously known for H an affine subspace over a prime field. The tools of higher-order Fourier analysis have found use in different areas of computer science, including list decoding, algorithmic decomposition and testing. Using our new results, we revisit some of these areas. (i) For any fixed finite field K, we show that the list decoding radius of the generalized Reed Muller code over K equals the minimum distance of the code. (ii) For any fixed finite field K, we give a polynomial time algorithm to decide whether a given polynomial P: K^n -> K can be decomposed as a particular composition of lesser degree polynomials. (iii) For any fixed finite field K, we prove that all locally characterized affine-invariant properties of functions f: K^n -> K are testable with one-sided error.
Cite as

Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta. On Higher-Order Fourier Analysis over Non-Prime Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 23:1-23:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.APPROX-RANDOM.2016.23,
  author =	{Bhattacharyya, Arnab and Bhowmick, Abhishek and Gupta, Chetan},
  title =	{{On Higher-Order Fourier Analysis over Non-Prime Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{23:1--23:29},
  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.23},
  URN =		{urn:nbn:de:0030-drops-66463},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.23},
  annote =	{Keywords: finite fields, higher order fourier analysis, coding theory, property testing}
}
  • Refine by Author
  • 1 Bennett, Huck
  • 1 Bhattacharyya, Arnab
  • 1 Bhowmick, Abhishek
  • 1 Budzynska, Katarzyna
  • 1 Gupta, Chetan
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Discourse, dialogue and pragmatics
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Communication Strategies
  • 1 Computational Argumentation
  • 1 Discourse and Dialogue
  • 1 Lattices
  • 1 NP-hardness
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 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