Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Chakrabarti, Amit ; Swamy, Chaitanya (Ed.)We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchylike functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every k ≥ 5, we show that CSPs where the underlying predicate is a pure monarchy function on k variables have no nontrivial sketching approximation algorithm in o(√n) space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are nontrivially approximable by O(log(n)) space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computeraided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously.more » « less

Leonardi, Stefano ; Gupta, Anupam (Ed.)We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in {0,…,q−1}, we prove that improving over the trivial approximability by a factor of q requires Ω(n) space even on instances with O(n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires Ω(n) space. The key technical core is an optimal, q−(k−1)inapproximability for the Max kLINmod q problem, which is the Max CSP problem where every constraint is given by a system of k−1 linear equations mod q over k variables. Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any nontrivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of Max kLINmod q with k=q=2. For general CSPs in the streaming setting, prior results only yielded Ω(√n) space bounds. In particular no linear space lower bound was known for an approximation factor less than 1/2 for any CSP. Extending the work of Kapralov and Krachun to Max kLINmod q to k>2 and q>2 (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides nontrivial technical challenges that we overcome in this work.more » « less

Neuromorphic computing would benefit from the utilization of improved customized hardware. However, the translation of neuromorphic algorithms to hardware is not easily accomplished. In particular, building superconducting neuromorphic systems requires expertise in both supercon ducting physics and theoretical neuroscience, which makes such design particularly challenging. In this work, we aim to bridge this gap by presenting a tool and methodology to translate algorith mic parameters into circuit specifications. We first show the correspondence between theoretical neuroscience models and the dynamics of our circuit topologies. We then apply this tool to solve a linear system and implement Boolean logic gates by creating spiking neural networks with our superconducting nanowirebased hardware.more » « less

Neuromorphic computing would benefit from the utilization of improved customized hardware. However, the translation of neuromorphic algorithms to hardware is not easily accomplished. In particular, building superconducting neuromorphic systems requires expertise in both superconducting physics and theoretical neuroscience, which makes such design particularly challenging. In this work, we aim to bridge this gap by presenting a tool and methodology to translate algorithmic parameters into circuit specifications. We first show the correspondence between theoretical neuroscience models and the dynamics of our circuit topologies. We then apply this tool to solve a linear system and implement Boolean logic gates by creating spiking neural networks with our superconducting nanowirebased hardware.more » « less