SFT

Overview

Package

Class

Use

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

SFT
Class SFT

java.lang.Object
  SFT.SFT

public class SFT
extends java.lang.Object
extends java.lang.Object

An implementation of the SFT algorithm for finding the list of elements whose Fourier coefficients are significant (and their coefficients) for a given function ƒ: G → C, where G is a Cartesian product of finite groups (i.e. Z_N1 x ... x Z_Nk) described by a list of N_j's or an Abelian group described by a list of N_j's and the corresponding generators g_j's.

The implementation is based on the SFT algorithm described in "Learning Noisy Characters, Multiplication Codes, And Cryptographic Hardcore Predicates" (Adi Akavia, 2008, page 52).

This library is a project in CS workshop, TAU, Spring 2010.

Author:: Elizabeth Firman and Ariel Stolerman

Constructor Summary
`SFT()`

Method Summary
`static java.util.Map<java.lang.Long,Complex>`	`getSignificantElements(long[][] G, double tau, FiniteAbelianFunction func, int numOfIterations, double delta, double fInfNorm, double fEuclideanNorm, float deltaCoeff, float maCoeff, float mbCoeff, float etaCoeff)` Returns a map of the elements in G and their tau-significant coefficients in the given function with delta-confidence.
`static java.util.Map<java.lang.Long,Complex>`	`getSignificantElements(long[][] G, double tau, FiniteAbelianFunction func, int numOfIterations, long m_A, long m_B)` Returns a map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
`static java.util.Map<java.lang.Long,Complex>`	`getSignificantElements(long[][] G, double tau, FiniteAbelianFunction func, long m_A, long m_B)` Returns a map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
`static java.util.Map<long[],Complex>`	`getSignificantElements(long[] G, double tau, DirectProdFunction func, int numOfIterations, double delta, double fInfNorm, double fEuclideanNorm, float deltaCoeff, float maCoeff, float mbCoeff, float etaCoeff)` Returns a map of the elements in G and their tau-significant coefficients in the given function with delta-confidence.
`static java.util.Map<long[],Complex>`	`getSignificantElements(long[] G, double tau, DirectProdFunction func, long m_A, long m_B)` Returns a map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
`static java.util.Map<long[],Complex>`	`getSignificantElements(long[] G, double tau, DirectProdFunction func, long m_A, long m_B, int numOfIterations)` Returns a map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
`static SFT.SFTUtils.MatlabTemporaryRepositoryFiniteAbelian`	`runMatlabSFTPart1Internal(java.lang.Boolean isLogged, java.lang.Long[][] G, double tau, double delta_t, double fInfNorm, double fEuclideanNorm, float deltaCoeff, float maCoeff, float mbCoeff, float etaCoeff)` For inner use in the Matlab SFT scripts.
`static SFT.SFTUtils.MatlabTemporaryRepositoryFiniteAbelian`	`runMatlabSFTPart1Internal(java.lang.Boolean isLogged, java.lang.Long[][] G, double tau, long m_A, long m_B)` For inner use in the Matlab SFT scripts.
`static SFT.SFTUtils.MatlabTemporaryRepositoryDirectProd`	`runMatlabSFTPart1Internal(java.lang.Boolean isLogged, java.lang.Long[] G, double tau, double delta_t, double fInfNorm, double fEuclideanNorm, float deltaCoeff, float maCoeff, float mbCoeff, float etaCoeff)` For inner use in the Matlab SFT scripts.
`static SFT.SFTUtils.MatlabTemporaryRepositoryDirectProd`	`runMatlabSFTPart1Internal(java.lang.Boolean isLogged, java.lang.Long[] G, double tau, long m_A, long m_B)` For inner use in the Matlab SFT scripts.
`static SFT.SFTUtils.MatlabTemporaryResultFiniteAbelian`	`runMatlabSFTPart2Internal(java.lang.Long[][] G, double tau, SFT.SFTUtils.MatlabTemporaryRepositoryFiniteAbelian matlabRep, int numOfIterations)` For inner use in the Matlab SFT scripts.
`static SFT.SFTUtils.MatlabTemporaryResultDirectProd`	`runMatlabSFTPart2Internal(java.lang.Long[] G, double tau, SFT.SFTUtils.MatlabTemporaryRepositoryDirectProd matlabRep, int numOfIterations)` For inner use in the Matlab SFT scripts.

Methods inherited from class java.lang.Object
`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

SFT

public SFT()

Method Detail

getSignificantElements

public static java.util.Map<long[],Complex> getSignificantElements(long[] G,
                                                                   double tau,
                                                                   DirectProdFunction func,
                                                                   long m_A,
                                                                   long m_B)
                                                            throws SFTException,
                                                                   FunctionException

Returns a map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values. Here m_A and m_B are given directly by the user for calculating the sizes of groups A, Btl where Q = {x-y | x in A, y in Btl}, instead of the original algorithm that calculates m_A and m_B by given parameters. This version of the function runs only one iteration of the original SFT algorithm.

Parameters:: G - The values N1,...,Nk describing the group G = Z_N1 x ... x Z_Nk.; tau - The threshold such that all tau-significant elements are returned.; func - The given function over G -> C whose elements and their significant coefficients are returned. Used for query access.; m_A - The size of the group A (for constructing the group Q).; m_B - The size of the groups Btl (for constructing the group Q).
Returns:: A map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
Throws:: SFTException - If the given parameters are invalid.; FunctionException - If the creation of the difference function between iterations of the SFT procedure is invalid. Should not be thrown in this version.

getSignificantElements

public static java.util.Map<long[],Complex> getSignificantElements(long[] G,
                                                                   double tau,
                                                                   DirectProdFunction func,
                                                                   long m_A,
                                                                   long m_B,
                                                                   int numOfIterations)
                                                            throws SFTException,
                                                                   FunctionException

Parameters:: G - The values N1,...,Nk describing the group G = Z_N1 x ... x Z_Nk.; tau - The threshold such that all tau-significant elements are returned.; func - The given function over G -> C whose elements and their significant coefficients are returned. Used for query access.; m_A - The size of the group A (for constructing the group Q).; m_B - The size of the groups Btl (for constructing the group Q).; numOfIterations - The number of SFT procedure iterations to run. Each iteration is ran with the difference function of the given function and the output of the previous SFT iteration. This is an optimization for the original SFT algorithm to enable catching significant coefficients with greater precision.
Returns:: A map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
Throws:: SFTException - If the given parameters are invalid.; FunctionException - If the creation of the difference function between iterations of the SFT procedure is invalid.

getSignificantElements

public static java.util.Map<long[],Complex> getSignificantElements(long[] G,
                                                                   double tau,
                                                                   DirectProdFunction func,
                                                                   int numOfIterations,
                                                                   double delta,
                                                                   double fInfNorm,
                                                                   double fEuclideanNorm,
                                                                   float deltaCoeff,
                                                                   float maCoeff,
                                                                   float mbCoeff,
                                                                   float etaCoeff)
                                                            throws SFTException,
                                                                   FunctionException

Returns a map of the elements in G and their tau-significant coefficients in the given function with delta-confidence. The algorithm includes a calculation of the error-bound, based on the delta-input and a some constant. This implementation allows the user (who knows the algorithm) to state this constant. The algorithm also includes calculations of randomly generated sets of elements in G, of sizes defined as m_A and m_B in the paper, that use some constants. This implementation allows the user (who knows the algorithm) to state these constants as well.

Parameters:: G - The values N1,...,Nk describing the group G = Z_N1 x ... x Z_Nk.; tau - The threshold such that all tau-significant elements are returned.; func - The given function over G -> C whose Fourier coefficients (elements) are returned. Used for query access.; numOfIterations - The number of SFT procedure iterations to run. Each iteration is ran with the difference function of the given function and the output of the previous SFT iteration. This is an optimization for the original SFT algorithm to enable catching significant coefficients with greater precision.; delta - The confidence parameter such that the algorithm succeeds with probability 1-delta.; fInfNorm - The infinity norm of the function.; fEuclideanNorm - The Euclidean norm of the function.; deltaCoeff - A constant coefficient for the algorithm's calculation of delta.; maCoeff - A constant coefficient for the algorithm's calculation of m_A.; mbCoeff - A constant coefficient for the algorithm's calculation of m_B.; etaCoeff - A constant coefficient for the algorithm's calculation of eta (appears in m_A and m_B calculation).
Returns:: A map of the elements in G and their tau-significant coefficients in the given function with delta-confidence.
Throws:: SFTException - If the given parameters are invalid.; FunctionException - If the creation of the difference function between iterations of the SFT procedure is invalid.

getSignificantElements

public static java.util.Map<java.lang.Long,Complex> getSignificantElements(long[][] G,
                                                                           double tau,
                                                                           FiniteAbelianFunction func,
                                                                           long m_A,
                                                                           long m_B)
                                                                    throws SFTException

Parameters:: G - The values (g1,N1),...,(gk,Nk) describing the Abelian group G where gj are the corresponding generators for Nj.; tau - The threshold such that all tau-significant elements are returned.; func - The given function over G -> C whose elements and their significant coefficients are returned. Used for query access.; m_A - The size of the group A (for constructing the group Q).; m_B - The size of the groups Btl (for constructing the group Q).
Returns:: A map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
Throws:: SFTException - If the given parameters are invalid.; FunctionException - If the creation of the difference function between iterations of the SFT procedure is invalid. Should not be thrown in this version.

getSignificantElements

public static java.util.Map<java.lang.Long,Complex> getSignificantElements(long[][] G,
                                                                           double tau,
                                                                           FiniteAbelianFunction func,
                                                                           int numOfIterations,
                                                                           long m_A,
                                                                           long m_B)
                                                                    throws SFTException

Parameters:: G - The values (g1,N1),...,(gk,Nk) describing the Abelian group G where gj are the corresponding generators for Nj.; tau - The threshold such that all tau-significant elements are returned.; func - The given function over G -> C whose elements and their significant coefficients are returned. Used for query access.; numOfIterations - The number of SFT procedure iterations to run. Each iteration is ran with the difference function of the given function and the output of the previous SFT iteration. This is an optimization for the original SFT algorithm to enable catching significant coefficients with greater precision.; m_A - The size of the group A (for constructing the group Q).; m_B - The size of the groups Btl (for constructing the group Q).
Returns:: A map of the elements in G and their tau-significant coefficients in the given function with confidence set by the selection of the m_A and m_B values.
Throws:: SFTException - If the given parameters are invalid.; FunctionException - If the creation of the difference function between iterations of the SFT procedure is invalid.

getSignificantElements

public static java.util.Map<java.lang.Long,Complex> getSignificantElements(long[][] G,
                                                                           double tau,
                                                                           FiniteAbelianFunction func,
                                                                           int numOfIterations,
                                                                           double delta,
                                                                           double fInfNorm,
                                                                           double fEuclideanNorm,
                                                                           float deltaCoeff,
                                                                           float maCoeff,
                                                                           float mbCoeff,
                                                                           float etaCoeff)
                                                                    throws SFTException

Parameters:: G - The values (g1,N1),...,(gk,Nk) describing the Abelian group G where gj are the corresponding generators for Nj.; tau - The threshold such that all tau-significant elements are returned.; func - The given function over G -> C whose Fourier coefficients (elements) are returned. Used for query access.; numOfIterations - The number of SFT procedure iterations to run. Each iteration is ran with the difference function of the given function and the output of the previous SFT iteration. This is an optimization for the original SFT algorithm to enable catching significant coefficients with greater precision.; delta - The confidence parameter such that the algorithm succeeds with probability 1-delta.; fInfNorm - The infinity norm of the function.; fEuclideanNorm - The Euclidean norm of the function.; deltaCoeff - A constant coefficient for the algorithm's calculation of delta.; maCoeff - A constant coefficient for the algorithm's calculation of m_A.; mbCoeff - A constant coefficient for the algorithm's calculation of m_B.; etaCoeff - A constant coefficient for the algorithm's calculation of eta (appears in m_A and m_B calculation).
Returns:: A map of the elements in G and their tau-significant coefficients in the given function with delta-confidence.
Throws:: SFTException - If the given parameters are invalid.; FunctionException - If the creation of the difference function between iterations of the SFT procedure is invalid.