User contributions for Admin

15 February 2023

• 10:5310:53, 15 February 2023 diff hist +345‎ N Integer linear program Vazirani (Unweighted Set-Covering; Weighted Set-Covering The Set-Covering Problem) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(U)$ words () == Description == ILP == Approximate? == Approximate Approximation Factor: \log n == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2001 == Reference == https://link.springer.com/chapter/10.1007/978-3-662-04565-7_13" current
• 10:5310:53, 15 February 2023 diff hist +356‎ N Greedy Algorithm ( The Set-Covering Problem) ‎ Created page with "== Time Complexity == $O(n^{3} log n)$ == Space Complexity == $O(U)$ words () == Description == == Approximate? == Approximate Approximation Factor: \ln(n) - \ln(\ln(n)) + \Theta(1) == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/237814.237991"
• 10:5310:53, 15 February 2023 diff hist +308‎ N Puterman Modified Policy Iteration (MPI) (Optimal Policies for MDPs Optimal Policies for MDPs) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Only needs to store values (V) and policy (pi), both size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +356‎ N Howard Policy Iteration (PI) (Optimal Policies for MDPs Optimal Policies for MDPs) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Only needs to store values (V) and policy (pi), both size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference == http://web.mit.edu/dimitrib/www/dpchapter.pdf" current
• 10:5310:53, 15 February 2023 diff hist +348‎ N Bellman Value Iteration (VI) (Optimal Policies for MDPs Optimal Policies for MDPs) ‎ Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(n)$ words (Only needs to store values (V) and policy (pi), both size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1957 == Reference == https://www.jstor.org/stable/24900506" current
• 10:5310:53, 15 February 2023 diff hist +287‎ N Ocone (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/978-1-4612-1784-8_28" current
• 10:5310:53, 15 February 2023 diff hist +436‎ N Del Moral; Pierre (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == https://projecteuclid.org/journals/annals-of-applied-probability/volume-8/issue-2/Measure-valued-processes-and-interacting-particle-systems-Application-to-nonlinear/10.1214/aoap/1028903535.full" current
• 10:5310:53, 15 February 2023 diff hist +303‎ N Damiano Brigo; Bernard Hanzon and François LeGland (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{2.45} logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == https://ieeexplore.ieee.org/abstract/document/661075"
• 10:5310:53, 15 February 2023 diff hist +341‎ N Maybeck; Peter S Extended Kalman Filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{2} log^{2} n)$ == Space Complexity == $O(n^{2})$? words (Generally works with a constant number of O(n)*O(n)-sized matrices per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference =="
• 10:5310:53, 15 February 2023 diff hist +277‎ N Zakai (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == https://link.springer.com/article/10.1007/BF00536382" current
• 10:5310:53, 15 February 2023 diff hist 0‎ Stratonovich (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎No edit summary
• 10:5310:53, 15 February 2023 diff hist +441‎ N Kushner non-linear filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$?? words (Generally works with a constant number of non-linear transformations; assumes that the description of the non-linear transformations is O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1967 == Reference == https://ieeexplore.ieee.org/document/1098671" current
• 10:5310:53, 15 February 2023 diff hist +222‎ N Stratonovich (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1959 == Reference =="
• 10:5310:53, 15 February 2023 diff hist +331‎ N Kalman Filter (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Generally works with a constant number of O(n)*O(n)-sized matrices per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1960 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +348‎ N Particle filter Del Moral (Filtering Problem (Stochastic Processes) Filtering Problem (Stochastic Processes)) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(nN)$? words (Works with O(N) number of O(n)-sized vectors (containing information about particles) each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1996 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +307‎ N Cholesky Decomposition (Matrix Factorization Collaborative Filtering) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores (intermediate steps of) factorization) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1983 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +307‎ N QR Matrix Decomposition (Matrix Factorization Collaborative Filtering) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores (intermediate steps of) factorization) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1955 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +307‎ N LU Matrix Decomposition (Matrix Factorization Collaborative Filtering) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Computes and stores (intermediate steps of) factorization) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1945 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +301‎ N Alpha-HMM (Matsuyama, Yasuo) (Maximum Likelihood Methods in Unknown Latent Variables, Hidden Markov Models Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{2} log^{2} n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2011 == Reference == https://ieeexplore.ieee.org/abstract/document/7895145"
• 10:5310:53, 15 February 2023 diff hist +446‎ N Shaban; Amirreza; Mehrdad; Farajtabar (Maximum Likelihood Methods in Unknown Latent Variables; multi-view model, discrete observations Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{2} log^{2} n)$ == Space Complexity == $O(kd+d^{3})$?? words (vector of parameters has size at least Theta(kd), and tensor M has size at least Theta(d^3) in paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2015 == Reference == https://faculty.cc.gatech.edu/~bboots3/files/SpectralExteriorPoint-NIPSWorkshop.pdf"
• 10:5310:53, 15 February 2023 diff hist +518‎ N Α-EM Algorithm (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of alpha-log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2003 == Reference == https://waseda.pure.elsevier.com/en/publications/the-%CE%B1-em-algorithm-surrogat..." current
• 10:5310:53, 15 February 2023 diff hist +424‎ N Expectation conditional maximization either (ECME) (Liu; Chuanhai; Rubin; Donald B) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1994 == Reference == https://www.jstor.org/stable/2337067" current
• 10:5310:53, 15 February 2023 diff hist +476‎ N Expectation conditional maximization (ECM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1993 == Reference == https://academic.oup.com/biomet/article-abstract/80/2/267/251605?redirectedFrom=fulltext" current
• 10:5310:53, 15 February 2023 diff hist +480‎ N EM with Quasi-Newton Methods (Jamshidian; Mortaza; Jennrich; Robert I.) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{2} log^{3} n)$ == Space Complexity == $O(n+r^{2})$? words (Stores current theta and Hessian matrix guess, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1997 == Reference == https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/1467-9868...."
• 10:5310:53, 15 February 2023 diff hist +424‎ N Expectation-Maximization (EM) algorithm (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://www.jstor.org/stable/2984875" current
• 10:5310:53, 15 February 2023 diff hist +276‎ N SPRINGBORN B.; SCHROEDER P.; PINKALL U. 2008 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n log^{2}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == https://dl.acm.org/doi/10.1145/1399504.1360676"
• 10:5310:53, 15 February 2023 diff hist +298‎ N BEN-CHEN M.; GOTSMAN C.; BUNIN G. 2008 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n log^{2}n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == http://www.cs.technion.ac.il/~gotsman/AmendedPubl/Miri/EG08_Conf.pdf"
• 10:5310:53, 15 February 2023 diff hist +225‎ N YANG Y.; KIM J.; LUO F.; HU S.; GU X. 2008 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(nloglogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference =="
• 10:5310:53, 15 February 2023 diff hist +271‎ N CHEN Z. G.; LIU L. G.; ZHANG Z. Y.; WANG G. J. 2007 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2007 == Reference == https://dl.acm.org/doi/10.1145/1236246.1236287" current
• 10:5310:53, 15 February 2023 diff hist +308‎ N ZAYER R.; ROESSL C.; SEIDEL H.-P 2005 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.226.1150&rep=rep1&type=pdf"
• 10:5310:53, 15 February 2023 diff hist +454‎ N YOSHIZAWA S.; BELYAEV A. G.; SEIDEL H.-P 2004 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://www.researchgate.net/profile/Alexander_Belyaev5/publication/47861414_A_fast_and_simple_stretch-minimizing_mesh_parameterization/links/5b962a6292851c78c40c0c3f/A-fast-and-simple-stretch-minimizing-mesh-parameterization.pdf" current
• 10:5310:53, 15 February 2023 diff hist +222‎ N YAN J. Q.; YANG X.; SHI P. F 2006 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference ==" current
• 10:5310:53, 15 February 2023 diff hist +273‎ N SANDER P. V.; SNYDER J.; GORTER S. J.; HOPPE 2001 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://dl.acm.org/doi/pdf/10.1145/383259.383307" current
• 10:5310:53, 15 February 2023 diff hist +267‎ N ZAYER R.; LÉVY B.; SEIDEL H.-P. 2007 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2007 == Reference == https://dl.acm.org/doi/10.5555/1281991.1282010" current
• 10:5310:53, 15 February 2023 diff hist +269‎ N SHEFFER A.; LÉVY B.; MOGILNITSKY M.; BOGOMYAKOV A. 2005 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://hal.inria.fr/inria-00105689/document" current
• 10:5310:53, 15 February 2023 diff hist +277‎ N SHEFFER A.; DE STURLER E. 2000 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://link.springer.com/article/10.1007/PL00013391" current
• 10:5310:53, 15 February 2023 diff hist +370‎ N HORMANN K.; GREINER G 1999 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.semanticscholar.org/paper/MIPS%3A-An-Efficient-Global-Parametrization-Method-Hormann-Greiner/a2f7f69b37565eb2729b45a7d72c6aae2e4908b8" current
• 10:5310:53, 15 February 2023 diff hist +324‎ N KARNI Z.; GOTSMAN C.; GORTLER S. J. 2005 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://dash.harvard.edu/bitstream/handle/1/2634388/Gortler_FreeBoundary.pdf?sequence=2&isAllowed=y" current
• 10:5310:53, 15 February 2023 diff hist +298‎ N LÉVY B.; PETITJEAN S.; RAY N.; MAILLOT J 2002 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n log^{2.5} n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://members.loria.fr/Bruno.Levy/papers/LSCM_SIGGRAPH_2002.pdf"
• 10:5310:53, 15 February 2023 diff hist +269‎ N DESBRUN M.; MEYER M.; ALLIEZ P. 2002 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/566654.566588" current
• 10:5310:53, 15 February 2023 diff hist +318‎ N FLOATER 2003 (Mesh Parameterization Mesh Parameterization) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://www.ams.org/journals/mcom/2003-72-242/S0025-5718-02-01466-7/S0025-5718-02-01466-7.pdf" current
• 10:5310:53, 15 February 2023 diff hist +389‎ N Hentenryck et. al. (Arc Consistency? Stable Matching Problem) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$? words (https://www.sciencedirect.com/science/article/abs/pii/000437029290020X) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/abs/pii/000437029290020X" current
• 10:5310:53, 15 February 2023 diff hist +362‎ N Manlove; Malley (Stable Marriage Problem Stable Matching Problem) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an $O(n^2)$-size CSP instance?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~davidm/pubs/7981.pdf" current
• 10:5310:53, 15 February 2023 diff hist +374‎ N Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf" current
• 10:5310:53, 15 February 2023 diff hist +377‎ N Irving's Algorithm (Stable Roommates Problem Stable Matching Problem) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Manipulates the $O(n)$-many $O(n)$-size preference lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/roommates/papers/Comp_sdarticle.pdf" current
• 10:5310:53, 15 February 2023 diff hist +356‎ N Berlekamp–Massey algorithm (Cryptanalysis of Linear Feedback Shift Registers Cryptanalysis of Linear Feedback Shift Registers) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(N)$? words (Computes and stores constant number of polynomials of degree $O(N)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1054260"
• 10:5310:53, 15 February 2023 diff hist +517‎ N Victor Shoup's algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is $O(n)$ so the total number of terms to keep track of is $O(n)$. Also, polynomials in the separating set can be computed in $O(n)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.co..." current
• 10:5310:53, 15 February 2023 diff hist +521‎ N Cantor–Zassenhaus algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) ‎ Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is O(n) so the total number of terms to keep track of is O(n). Also, computing h^{((q^d-1)/2)}-1 mod f only requires O(n) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.ams.org/journals/mcom/1..."
• 10:5310:53, 15 February 2023 diff hist +417‎ N Distinct-degree factorization (Distinct-degree Factorization of Polynomials Over Finite Fields) ‎ Created page with "== Time Complexity == $O(n^{3} + nlogn)$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration. Note that computing $gcd(f, x^{(q^i)}-x)$ can be cleverly done in $O(n)$ space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1944 == Reference == -"
• 10:5310:53, 15 February 2023 diff hist +245‎ N Schubert's algorithm ( Factorization of Polynomials Over Finite Fields) ‎ Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -" current