skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 10:00 PM to 12:00 PM ET on Tuesday, March 25 due to maintenance. We apologize for the inconvenience.


Title: Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV
Award ID(s):
1909429
PAR ID:
10347531
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Page Range / eLocation ID:
1501 to 1514
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Manipulating the electromagnetic (EM) scattering behavior from an arbitrary surface dynamically on arbitrary design goals is an ultimate ambition for many EM stealth and communication problems, yet it is nearly impossible to accomplish with conventional analysis and optimization techniques. Here we present a reconfigurable conformal metasurface prototype as well as a workflow that enables it to respond to multiple design targets on the reflection pattern with extremely low on-site computing power and time. The metasurface is driven by a sequential tandem neural network which is pre-trained using actual experimental data, avoiding any possible errors that may arise from calculation, simulation, or manufacturing tolerances. This platform empowers the surface to operate accurately in a complex environment including varying incident angle and operating frequency, or even with other scatterers present close to the surface. The proposed data-driven approach requires minimum amount of prior knowledge and human effort yet provides maximized versatility on the reflection control, stepping towards the end form of intelligent tunable EM surfaces. 
    more » « less
  2. Abstract This paper is concerned with the explicit computation of the limiting distribution function of the largest real eigenvalue in the real Ginibre ensemble when each real eigenvalue has been removed independently with constant likelihood. We show that the recently discovered integrable structures in [2] generalize from the real Ginibre ensemble to its thinned equivalent. Concretely, we express the aforementioned limiting distribution function as a convex combination of two simple Fredholm determinants and connect the same function to the inverse scattering theory of the Zakharov–Shabat system. As corollaries, we provide a Zakharov–Shabat evaluation of the ensemble’s real eigenvalue generating function and obtain precise control over the limiting distribution function’s tails. The latter part includes the explicit computation of the usually difficult constant factors. 
    more » « less
  3. Abstract There is a growing interest in leveraging functional programming languages in real-time and embedded contexts. Functional languages are appealing as many are strictly typed, amenable to formal methods, have limited mutation, and have simple but powerful concurrency control mechanisms. Although there have been many recent proposals for specialized domain-specific languages for embedded and real-time systems, there has been relatively little progress on adapting more general purpose functional languages for programming embedded and real-time systems. In this paper, we present our current work on leveraging Standard ML (SML) in the embedded and real-time domains. Specifically, we detail our experiences in modifying MLton, a whole-program optimizing compiler for SML, for use in such contexts. We focus primarily on the language runtime, reworking the threading subsystem, object model, and garbage collector. We provide preliminary results over a radar-based aircraft collision detector ported to SML. 
    more » « less