{"entities":{"Q687506":{"pageid":689355,"ns":120,"title":"Item:Q687506","lastrevid":47195521,"modified":"2025-12-31T23:35:37Z","type":"item","id":"Q687506","labels":{"en":{"language":"en","value":"Exponential lower bounds for the pigeonhole principle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 431311"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$F74F87FA-51AE-43E6-9C80-D2EA77332ABD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"279c95764928edb887e987b60fea9cb7d0cb1275","datavalue":{"value":{"text":"Exponential lower bounds for the pigeonhole principle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q687506$68F4E77C-2641-4B76-AC57-AF12E69FD0E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aaf8a5168af7e2b47b5f047fa86a0249437a15ae","datavalue":{"value":"0784.03034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$A4E57968-F4FE-4AB3-919C-7F926CC7B602","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5fb00eaf5277807c9920daec08b6d94cb146f4bd","datavalue":{"value":"10.1007/BF01200117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$D6CFFED2-D0B1-4B05-9A07-8C38E63750B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38b40ed6cb099fba5da493703b11839c0af89042","datavalue":{"value":{"entity-type":"item","numeric-id":202089,"id":"Q202089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$8F754B25-3734-40B5-9F7B-3587AA617F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afbdf0b4b75e6a0dfd1ecc76c9480c04f5fced5d","datavalue":{"value":{"entity-type":"item","numeric-id":202088,"id":"Q202088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$61C9CEDC-25A9-4FA6-BDC7-4AED01F1A8E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bdeac5e928e087a649bdeced20db2b34fab0678f","datavalue":{"value":{"entity-type":"item","numeric-id":1822913,"id":"Q1822913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$78142433-D070-4F7F-ACA8-DF87A012680B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$DE0B4BCE-CCDB-4DEF-AC09-774D5799CECB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"754b3b51d809379c8c8e6b0470743f1e863a6c78","datavalue":{"value":{"time":"+1993-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q687506$FBB486C6-7AD5-41F2-9767-3B6CD0668469","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd9ddc8913b6f92188d0295e64b6957904f0341f","datavalue":{"value":"The paper deals with complexity of Frege proofs for the (propositional) pigeonhole principle (\\(\\text{PHP}_ n\\) for all natural \\(n\\)). It shows an exponential lower bound on the size of proofs with bounded depth (of logical connectives in formulas). Thus the previously known superpolynomial lower bound by Ajtai has been improved.   As a corollary, the authors obtained an \\(\\Omega(\\log\\log n)\\) lower bound on depth for polynomial-size Frege proofs of \\(\\text{PHP}_ n\\). It is close to the precise complexity since Buss has constructed polynomial- size, logarithmic-depth proofs for \\(\\text{PHP}_ n\\).   The proof goes by induction on the depth -- using a certain approximation of the depth \\(d\\) formulas by some depth \\(d-1\\) formulas, the base case being dealt with separately. The key point is a combinatorial lemma similar to the switching lemma used by Hastad.   The authors also mention the open problem whether the weak \\(\\text{PHP}_ n\\) (there is no \\(1-1\\) map of \\([2n]\\) to \\([n]\\)) has constant-depth proofs of polynomial size. The main result of the paper was independently obtained by Kraj\u00ed\u010dek, Pudl\u00e1k and Woods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q687506$3B2C87CB-2552-44EC-8F90-7C5414C946D5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aa98ea30b6abca7b476f74745e2df6c0f45b70be","datavalue":{"value":{"entity-type":"item","numeric-id":672325,"id":"Q672325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$2EB70FDF-246B-4383-ACAD-2691D3DE678C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$892D0D9C-75E0-40F7-A76D-43E2D025359A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"02303c61036060136df3f7b7e22c52163746633f","datavalue":{"value":"68Q99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$C78D9110-057E-4E91-886A-95EE32421E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$4FDE8CEB-D301-47F4-896C-2748BB9FE9EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$DFF699BD-49E2-411D-9CBA-D89401BED532","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be4c7d095f6c1761d9dfbdf66f3b995adb9f7e4c","datavalue":{"value":"431311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$C54D5E69-14C0-4948-83AA-EBA6FF0C26F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b24e51e460d663f6ecf18860b761adb8bb29e572","datavalue":{"value":"propositional proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q687506$702EA191-AC24-4328-939C-C76A0BD42FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f8136f791f6d4ba5b9b84080baf4aeab34158b5","datavalue":{"value":"complexity of Frege proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q687506$7B967B4A-2D52-40C3-9FA2-2A79BAE7C50D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b8e7d033342c99b72c744e65e5d3e8084428c65","datavalue":{"value":"pigeonhole principle","type":"string"},"datatype":"string"},"type":"statement","id":"Q687506$9939B848-5704-4965-804D-CE6BA6E5FDDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce9d1647b20c82d33b2f1629c4eaaf4984386a1b","datavalue":{"value":"exponential lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q687506$A9D65CBA-6F78-4A1B-B87E-88D11FA25311","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"405a9d8026a2611523cdd26531e1bff956b8bf1c","datavalue":{"value":"Q56812988","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q687506$BA25B1EC-8C23-41E5-81A2-6D7554DCD073","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$4E068964-96E0-4BC2-B1F3-6C81BE0FBFAA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$665B75F9-6367-4956-A70E-F5196B790C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7dd417123888bb50a422ec215ff530d2d3769a","datavalue":{"value":{"entity-type":"item","numeric-id":919820,"id":"Q919820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$9AD0FACD-E3E8-4C20-BF23-4EF96A94D8ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb44e08a53e4c007a1970cc14d1cf388b1586e9","datavalue":{"value":{"entity-type":"item","numeric-id":4710686,"id":"Q4710686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$6CAEEF1E-5F3F-475F-96FC-7363F8FB6520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01d92fa5008a947cf4d000f7551c40cd38c27e82","datavalue":{"value":{"entity-type":"item","numeric-id":4027856,"id":"Q4027856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$E5789CF3-E507-4514-A20D-A36AD7089F99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84f26cdf3dbb7656aa8d1a8c3c3f68e3d28b0f44","datavalue":{"value":{"entity-type":"item","numeric-id":3138022,"id":"Q3138022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$204BA451-D337-447A-9536-8C46782CFEDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f31cbeafb74eb2331031a6d2305fa02411af3e7","datavalue":{"value":{"entity-type":"item","numeric-id":3775553,"id":"Q3775553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$6B755792-7736-4E6B-A049-D6A8B614705F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$54FEF54D-6528-4494-AAE3-B27FAE316B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e39951d487d3bf563c62341ed381ea5be4f484","datavalue":{"value":{"entity-type":"item","numeric-id":3318683,"id":"Q3318683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$02CDE269-EEF8-4A4D-8180-90683F644E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec2fa04d400281f100817ce7e13bdaafd2683670","datavalue":{"value":{"entity-type":"item","numeric-id":1071750,"id":"Q1071750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$F468EC7F-8A14-4564-B10D-B7D9690D350F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de38041d8b6a97fdfbfcd7df074d9cf402d459e3","datavalue":{"value":{"entity-type":"item","numeric-id":4728251,"id":"Q4728251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$3476C6AA-854F-48E8-BEDD-5477C29E85CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3b936472256c474ab8250b72e7c010873198894","datavalue":{"value":{"entity-type":"item","numeric-id":4206725,"id":"Q4206725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$F53450CD-5D80-49C0-BDEE-954B37486CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcdbe2bfe0d10636cf929d8ea04a35b0746f5915","datavalue":{"value":{"entity-type":"item","numeric-id":687506,"id":"Q687506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$F51DB137-3219-4698-BC15-07775AD26954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728810277830424bd131e6e77eef399df584ccea","datavalue":{"value":{"entity-type":"item","numeric-id":3780485,"id":"Q3780485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q687506$81A98685-5B32-4766-9688-059E1000B4C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b8619ab5791ecf083dffaaaa18e3233c03cbac4","datavalue":{"value":{"entity-type":"item","numeric-id":4847394,"id":"Q4847394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c4394a77185f9b668fdbd139627803511eac192","datavalue":{"value":{"amount":"+0.941344678401947","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q687506$BBAB99B8-99A1-4B06-9BA7-7FB71166B71B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"217ca188c28e2635cf5bccb238de4f5c96411b6b","datavalue":{"value":{"entity-type":"item","numeric-id":1343166,"id":"Q1343166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a3fea6a33bcc649d1fb95a71f237dd07f5220f5","datavalue":{"value":{"amount":"+0.9412947297096252","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q687506$275E6E65-EC03-4A32-8359-A148373BB58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0b36f4f048ba74d5c86c997359e7b201233c52a","datavalue":{"value":{"entity-type":"item","numeric-id":4651534,"id":"Q4651534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be2e8786aeae29cc444f744cc45982c13fae90c6","datavalue":{"value":{"amount":"+0.8898535370826721","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q687506$0AB39A66-785B-45F2-B6F4-06D97AE589D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8111f0c19f92dbadfd4732ee48029b08b6bd9bfd","datavalue":{"value":{"entity-type":"item","numeric-id":4027856,"id":"Q4027856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a45212be6da4397c50a218a19d0f9a5445ac24dd","datavalue":{"value":{"amount":"+0.8684953451156616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q687506$45DD9620-143A-44EF-968D-D25306A7AB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"920457f19cccdcc190f02a78940b201d37b13ad8","datavalue":{"value":{"entity-type":"item","numeric-id":4549235,"id":"Q4549235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d709565329fc864e3da0532a2399f8de0336f43d","datavalue":{"value":{"amount":"+0.8683298826217651","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q687506$ECE24696-2901-4807-AF62-570EB8FA48F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:687506","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:687506"}}}}}