More Like this

1. Approximating Observables Is as Hard as Counting

   Galanis, Andreas; Štefankovič, Daniel; Vigoda, Eric (June 2022, ICALP 2022)

   We study the computational complexity of estimating local observables for Gibbs distributions. A simple combinatorial example is the average size of an independent set in a graph. A recent work of Galanis et al (2021) established NP-hardness of approximating the average size of an independent set utilizing hardness of the corresponding optimization problem and the related phase transition behavior. We instead consider settings where the underlying optimization problem is easily solvable. Our main contribution is to classify the complexity of approximating a wide class of observables via a generic reduction from approximate counting to the problem of estimating local observables. The key idea is to use the observables to interpolate the counting problem. Using this new approach, we are able to study observables on bipartite graphs where the underlying optimization problem is easy but the counting problem is believed to be hard. The most-well studied class of graphs that was excluded from previous hardness results were bipartite graphs. We establish hardness for estimating the average size of the independent set in bipartite graphs of maximum degree 6; more generally, we show tight hardness results for general vertex-edge observables for antiferromagnetic 2-spin systems on bipartite graphs. Our techniques go beyond 2-spin systems, and for the ferromagnetic Potts model we establish hardness of approximating the number of monochromatic edges in the same region as known hardness of approximate counting results. 

   more » « less
2. Approximating Observables Is as Hard as Counting

   Galanis, Andreas; Štefankovič, Daniel; Vigoda, Eric (July 2022, Leibniz international proceedings in informatics)
3. Text Embeddings Reveal (Almost) As Much As Text

   https://doi.org/10.18653/v1/2023.emnlp-main.765  

   Morris, John; Kuleshov, Volodymyr; Shmatikov, Vitaly; Rush, Alexander (January 2023, Association for Computational Linguistics)
4. From graphs as task to graphs as tool

   https://doi.org/10.1002/tea.21930  

   Stephens, A Lynn (May 2024, Journal of Research in Science Teaching)

   Abstract It is widely recognized that we need to prepare students to think with data. This study investigates student interactions with digital data graphs and seeks to identify what might prompt them to shift toward using their graphs as thinking tools in the authentic activity of doing science. Drawing from video screencast data of three small groups engaged in sensor‐based and computer simulation‐based experiments in high school physics classes, exploratory qualitative methods are used to identify the student interactions with their graphs and what appeared to prompt shifts in those interactions. Analysis of the groups, one from a 9th grade class and two from 11th/12th grade combined classes, revealed that unexpected data patterns and graphical anomalies sometimes, but not always, preceded deeper engagement with the graphs. When shifts toward deeper engagement did occur, transcripts revealed that the students perceived the graphical patterns to be misaligned with the actions they had taken to produce those data. Misalignments between the physical, digital, and conceptual worlds of the investigations played an important role in these episodes, appearing to motivate students to revise either their experimental procedures or their conceptions of the phenomena being explored. If real‐time graphs can help foster a sense in students that there should be alignments between their data production and data representations, it is suggested that pedagogy leverage this as a way to support deeper student engagement with graphs. 

   more » « less
5. One world is (probably) just as good as many

   https://doi.org/10.1007/s11229-022-03499-z  

   Steeger, Jer (April 2022, Synthese)