{"id":"W2068462176","doi":"","title":"On distance to monotonicity and longest increasing subsequence of a data stream","year":2008,"lang":"en","type":"article","venue":"Symposium on Discrete Algorithms","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":31,"is_retracted":false,"has_abstract":true,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Monotonic function; Longest common subsequence problem; Subsequence; Longest increasing subsequence; Combinatorics; Upper and lower bounds; Mathematics; Conjecture; Sequence (biology); Approximation algorithm; Space (punctuation); Streaming algorithm; Set (abstract data type); Edit distance; Log-log plot; Data stream; Discrete mathematics; Binary logarithm; Algorithm; Computer science; Statistics; Bounded function","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":["metaepi_narrow"],"consensus_categories":[],"category_scores_codex":[0.0004771017,0.0003232079,0.0003949298,0.0002039774,0.0003242603,0.0001234356,0.002221622,0.0000801674,0.000005847762],"category_scores_gemma":[0.0001019907,0.0002973251,0.00006819605,0.0006987348,0.0003294615,0.0007627307,0.001081512,0.0002632848,0.00001694252],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00005959318,"about_ca_system_score_gemma":0.00009950606,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0005171836,"about_ca_topic_score_gemma":0.00004666286,"domain_scores_codex":[0.9972231,0.0001505665,0.0003998035,0.001133402,0.0006237393,0.0004693532],"domain_scores_gemma":[0.9968167,0.0004144533,0.0001597915,0.002230967,0.00008718562,0.0002909369],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.001164134,0.0024458,0.01155118,0.0003786283,0.0004064653,0.001283779,0.008608955,0.004053067,0.01672835,0.7282097,0.002527473,0.2226425],"study_design_scores_gemma":[0.003960877,0.005937214,0.08073746,0.001676988,0.00009029858,0.0009245416,0.0002251955,0.8210732,0.03507849,0.04031711,0.006183539,0.00379505],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.6036962,0.000369426,0.3870234,0.002924781,0.000505661,0.000795806,0.0005429103,0.0003018031,0.003839985],"genre_scores_gemma":[0.9122392,0.0002153601,0.08697618,0.0003576365,0.00007830928,0.00001819009,0.00002900328,0.00002065255,0.00006549988],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.8170202,"threshold_uncertainty_score":0.9999479,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.04200296111938706,"score_gpt":0.285111851134366,"score_spread":0.243108890014979,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}