{"id":"W326289323","doi":"10.1007/978-3-642-02017-9_29","title":"Kolmogorov Complexity and Combinatorial Methods in Communication Complexity","year":2009,"lang":"en","type":"article","venue":"Lecture notes in computer science","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":false,"ca_institutions":"Université de Montréal","funders":"","keywords":"Kolmogorov complexity; Communication complexity; Kolmogorov structure function; Minimax; Mathematics; Upper and lower bounds; Worst-case complexity; Quantum complexity theory; Mutual information; Intuition; Computational complexity theory; Dimension (graph theory); Discrete mathematics; Matching (statistics); Kolmogorov equations (Markov jump process); Theoretical computer science; Computer science; Quantum; Combinatorics; Time complexity; Algorithm; Mathematical optimization; Quantum information; Statistics","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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.004522475,0.001759665,0.002350166,0.004688249,0.00269335,0.007943159,0.003176848,0.004127171,0.01184458],"category_scores_gemma":[0.02343925,0.001176081,0.002354434,0.005968049,0.01112438,0.02710919,0.003374142,0.01130629,0.001433725],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.004978146,"about_ca_system_score_gemma":0.001781665,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001712017,"about_ca_topic_score_gemma":0.001252666,"domain_scores_codex":[0.9958412,0.001835082,0.0002578836,0.000601762,0.00116384,0.0003001661],"domain_scores_gemma":[0.9592794,0.03598513,0.0008426644,0.00196379,0.001435946,0.0004930241],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.000005653298,0.000009204334,0.00009047821,0.00005390375,0.000006763176,0.00001189889,0.00004437529,0.001488649,0.00003933338,0.9943176,0.001424497,0.002507642],"study_design_scores_gemma":[0.000003579117,0.000002596201,0.00005933836,0.00001441639,0.000004710115,0.00001580075,0.00001598717,0.005557714,0.00004148427,0.9919969,0.002280806,0.000006510828],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"methods","genre_scores_codex":[0.02256451,0.03116348,0.8290741,0.03263731,0.001487706,0.00008896837,0.0008182315,0.000365013,0.08180063],"genre_scores_gemma":[0.7137038,0.03963132,0.1931297,0.004686287,0.01382667,0.0008827266,0.001321098,0.0004736544,0.03234475],"genre_candidate":"methods","genre_consensus":"methods","teacher_disagreement_score":0.01184458,"threshold_uncertainty_score":0.03962404,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.04707098481877801,"score_gpt":0.3411465336750322,"score_spread":0.2940755488562541,"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."}}