Approximating function properties with expander graphs
AssigneeMicrosoft Corporation
InventorsKristin E Lauter, Denis X. Charles, Eyal Zvi Goren
Life of this patent
Estimating the term…
Abstract
Function properties may be approximated using an expander graph. For example, an approximate average of a function may be determined by randomly exploring an expander graph. Values of the function are associated with vertices of the expander graph. The expander graph is randomly explored by traversing edges and encountering vertices. The exploration may comprise a crawl, a walk, and so forth. An approximate average of the function is determined based on the function values that are associated with encountered vertices.
Claims20
A method comprising:
- storing, in a memory storage media communicatively coupled to a processor, processor-executable instructions for performing the method;
- executing the instructions on the processor;
- according to the instructions being executed:
- associating respective values of a function with respective vertices of an expander graph;
- exploring the expander graph to encounter multiple vertices;
- ascertaining respective function values that are associated with respective ones of the multiple encountered vertices;
- and
- calculating a property of the ascertained function values.
One or more processor-accessible storage media comprising processor-executable instructions that include an approximate average determiner that determines an approximate average of a function using an expander graph having multiple vertices and interconnecting edges.
A device comprising:
- an expander graph having vertices that are interconnected by edges, each vertex connected by edges to at least two other vertices;
- a function having values;
- and
- an approximate average determiner to associate the values of the function to the vertices of the expander graph, wherein the approximate average determiner encounters multiple vertices of the expander graph by exploring the expander graph responsive to a random seed and produces an approximate average for the function based on the values of the function that are associated with the multiple vertices that are encountered.
Dependencies are inferred from the claim text.