{"entities":{"Q7361332":{"pageid":31519535,"ns":120,"title":"Item:Q7361332","lastrevid":105364946,"modified":"2026-10-07T13:35:32Z","type":"item","id":"Q7361332","labels":{"en":{"language":"en","value":"Derandomization with Conditional Expectations"}},"descriptions":{"en":{"language":"en","value":"AFP entry Derandomization_Conditional_Expectations"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b85533bcc2420c73b6d3b10e9a86665c141841ab","datavalue":{"value":"https://isa-afp.org/entries/Derandomization_Conditional_Expectations.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361332$D86D090C-ADFE-450C-881D-F552717E102A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"946f9eb7a7737d88be41a6a799278842b1b41e8e","datavalue":{"value":{"time":"+2024-03-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361332$2A85A87B-0CFC-414C-8BE1-42EC1F5E140F","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"08e34730e8843d863438c2ad5795ad3f0ee72024","datavalue":{"value":"Emin Karayel","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361332$1D5A0093-8C2E-4756-9ADC-FF17504222C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3981bae5a9cb5531d422dfc34241faff69a9bf99","datavalue":{"value":{"text":"Derandomization with Conditional Expectations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361332$BEAB4A0A-A0B7-4AA0-9ED7-0BE110E8ACF7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7ecea1b6cdf0122922e291e3b4c0776fc02693e6","datavalue":{"value":"The Method of Conditional Expectations (sometimes also called \"Method of Conditional Probabilities\") is one of the prominent derandomization techniques. Given a randomized algorithm, it allows the construction of a deterministic algorithm with a result that matches the average-case quality of the randomized algorithm. Using this technique, this entry starts with a simple example, an algorithm that obtains a cut that crosses at least half of the edges. This is a well-known approximate solution to the Max-Cut problem. It is followed by a more complex and interesting result: an algorithm that returns an independent set matching (or exceeding) the Caro-Wei bound : $\\frac{n}{d+1}$ where $n$ is the vertex count and $d$ is the average degree of the graph. Both algorithms are efficient and deterministic, and follow from the derandomization of a probabilistic existence proof.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361332$1202AB86-993A-4C52-835E-EE94C4D3E386","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9208528a9398d42022a83d3910fdcc8477ab6c6","datavalue":{"value":{"entity-type":"item","numeric-id":2784326,"id":"Q2784326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$79C0AC99-D5AC-4B7A-AF75-07A7BFB6342C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bac7f1baaa55096d83c73bf345e8308c96e8d9b7","datavalue":{"value":{"entity-type":"item","numeric-id":4255576,"id":"Q4255576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$C2072727-DD3C-4B80-8252-1C925BBB76F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e81d90827a0aec8468b8c5d962de74cf4ef0e19","datavalue":{"value":{"entity-type":"item","numeric-id":1175993,"id":"Q1175993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$D3E31433-4524-4222-9685-1FF12939BF4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec5176ee43e6a858a1812de355e48370a8ffb310","datavalue":{"value":{"entity-type":"item","numeric-id":2869768,"id":"Q2869768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$7E8FC235-1DCC-4FE1-BBB9-374AAB244E30","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$4CEA560A-E24C-4F42-AB7C-6A1951A79C6F","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"246268cd0556371cd3845143f6d8755898b40ab0","datavalue":{"value":{"entity-type":"item","numeric-id":7361168,"id":"Q7361168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$50C49549-D403-488E-9C24-3AF2A351E0F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"4364ef645d61cdb1600e55c048bcbeb6b6b307a4","datavalue":{"value":{"entity-type":"item","numeric-id":7361238,"id":"Q7361238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$5060D92A-FE6F-4D86-A94E-29974FCDCD6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"568df032e4fa5e393d3cafa654f178d211e1f6f1","datavalue":{"value":{"entity-type":"item","numeric-id":7361689,"id":"Q7361689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$679169A1-E29C-4C96-BB89-C7D513A28FAA","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"83587c66a63f16aa6d09e1e557ca61651a36a985","datavalue":{"value":{"entity-type":"item","numeric-id":7360782,"id":"Q7360782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$6B9AEA77-A317-426D-9E44-751608C1C3DF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361332$B1D5A6AD-AC10-4AEA-BD3F-832B3C550192","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Derandomization with Conditional Expectations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Derandomization_with_Conditional_Expectations"}}}}}