# approximation Published articles for approximation. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## Remez and function approximations DevFeed: [Remez and function approximations]() Original publisher: [Read original article]() Published: 2024-05-06T17:18:29Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [FHE](), [homomorphic encryption](), [polynomials](), [Algorithm](), [Python]() Tags: [algorithm](), [approximation](), [article](), [fhe](), [homomorphic-encryption](), [how-to](), [library](), [optimization](), [polynomials](), [python](), [remez](), [shortform]() ### AI overview The article discusses approximating functions with low-degree polynomials for arithmetic fully homomorphic encryption. It examines lolremez, the Remez algorithm, Paterson-Stockmeyer evaluation, and a multi-interval Remez method for approximating discontinuous functions such as sign. ### Source excerpt I've been learning recently about how to approximate functions by low-degree polynomials. This is useful in fully homomorphic encryption (FHE) in the context of "arithmetic FHE" (see my FHE overview article), where the computational model makes low-degree polynomials cheap to evaluate and non-polynomial functions expensive or impossible. In browsing the state of the art I came across two interesting things. The first is the software package lolremez that implements polynomial (and rational polynomial $f(x) / g(x)$) function approximation using the so-called Remez algorithm. ## The Čech Complex and the Vietoris-Rips Complex DevFeed: [The Čech Complex and the Vietoris-Rips Complex]() Original publisher: [Read original article]() Published: 2015-08-06T09:00:00Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [data](), [datasets](), [Point cloud](), [Computing]() Tags: [approximation](), [cech-complex](), [complex](), [computational-topology](), [data-mining](), [data-science](), [dataset](), [homology](), [linear-algebra](), [mathematics](), [persistent-homology](), [point](), [points](), [simplicial-complex](), [vietoris-rips-complex]() ### AI overview This article introduces computational topology for analyzing the shape of data. It explains how point clouds can be converted into simplicial complexes so homology and persistent homology can identify qualitative features such as connected components and holes, with some resistance to noise. ### Source excerpt It's about time we got back to computational topology. Previously in this series we endured a lightning tour of the fundamental group and homology, then we saw how to compute the homology of a simplicial complex using linear algebra. What we really want to do is talk about the inherent shape of data. Homology allows us to compute some qualitative features of a given shape, i.e., find and count the number of connected components or a given shape, or the number of "2-dimensional holes" it has. ## When Greedy Algorithms are Good Enough: Submodularity and the (1--1/e)-Approximation DevFeed: [When Greedy Algorithms are Good Enough: Submodularity and the (1--1/e)-Approximation]() Original publisher: [Read original article]() Published: 2014-07-07T10:00:01Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Algorithms, Complexity](), [Algorithms](), [Computer science](), [Mathematics]() Tags: [algorithm](), [algorithms](), [approximation](), [approximation-algorithms](), [computer-science](), [coverage](), [greedy](), [greedy-algorithm](), [matroids](), [optimization](), [submodularity](), [theory]() ### AI overview This article explains when greedy algorithms can produce optimal or near-optimal solutions. It introduces submodularity as a diminishing-returns property and discusses how it can provide a reasonably good approximation to the optimal solution. ### Source excerpt Greedy algorithms are among the simplest and most intuitive algorithms known to humans. Their name essentially gives their description: do the thing that looks best right now, and repeat until nothing looks good anymore or you're forced to stop. Some of the best situations in computer science are also when greedy algorithms are optimal or near-optimal. There is a beautiful theory of this situation, known as the theory of matroids. We haven't covered matroids on this blog (edit: we did), but in this post we will focus on the next best thing: when the greedy algorithm guarantees a reasonably good approximation to the optimal solution. ## Community Detection in Graphs -- a Casual Tour DevFeed: [Community Detection in Graphs -- a Casual Tour]() Original publisher: [Read original article]() Published: 2014-05-19T10:00:32Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [Mathematics](), [Algorithms](), [Algorithms, Complexity]() Tags: [approximation](), [approximation-algorithms](), [cliques](), [clustering](), [community-detection](), [erdos-renyi](), [graph](), [graphs](), [mathematics](), [modularity](), [network](), [newman](), [np-hard](), [power-law-distribution](), [random-graph](), [randomized-algorithm](), [technical](), [walktrap]() ### AI overview This introductory article examines community detection in graphs. It explains the informal idea of a community, why defining one precisely and usefully is difficult, and how the clique-based approach leads to computationally intractable problems, including the NP-hardness of finding the largest clique. ### Source excerpt Graphs are among the most interesting and useful objects in mathematics. Any situation or idea that can be described by objects with connections is a graph, and one of the most prominent examples of a real-world graph that one can come up with is a social network. Recall, if you aren't already familiar with this blog's gentle introduction to graphs, that a graph $ G$ is defined by a set of vertices $ V$, and a set of edges $ E$, each of which connects two vertices. ## Streaming Median DevFeed: [Streaming Median]() Original publisher: [Read original article]() Published: 2012-06-14T22:03:55Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Streaming](), [Python](), [Algorithms](), [generators](), [iteration](), [Programming]() Tags: [algorithm](), [approximation](), [big-data](), [data-analysis](), [element](), [generators](), [implementation](), [infinite](), [input](), [iteration](), [mathematics](), [median](), [programming](), [python](), [sequence](), [streaming](), [streaming-data](), [yield]() ### AI overview This tutorial presents a Python generator that approximates the median of a potentially infinite integer sequence using constant space. The algorithm adjusts its current estimate by one for each input value that is above or below the estimate, and the article discusses how changing stream distributions affect the result. ### Source excerpt Problem: Compute a reasonable approximation to a "streaming median" of a potentially infinite sequence of integers. Solution: (in Python) def streamingMedian(seq): seq = iter(seq) m = 0 for nextElt in seq: if m > nextElt: m -= 1 elif m < nextElt: m += 1 yield m Discussion: Before we discuss the details of the Python implementation above, we should note a few things. First, because the input sequence is potentially infinite, we can't store any amount of information that is increasing in the length of the sequence.