{"entities":{"Q5894427":{"pageid":7933090,"ns":120,"title":"Item:Q5894427","lastrevid":55969654,"modified":"2026-02-21T15:13:08Z","type":"item","id":"Q5894427","labels":{"en":{"language":"en","value":"New degree bounds for polynomial threshold functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990558"}},"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":"Q5894427$BE12B978-35AA-4CFF-ACAF-C3908BC75188","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0d7ca44ea5ac2203b85061a3b03b78929ac07106","datavalue":{"value":{"text":"New degree bounds for polynomial threshold functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5894427$D6DA6680-E58B-4E21-9AF6-F8993227B386","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"166105cbce23e22637f7b835eb5305ed169e95d4","datavalue":{"value":"1240.05303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$AF2FD6D9-C45C-4146-9F1A-08F8DDDD1DEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3524eec4221edfc27dcb01251cc2bcd069e71002","datavalue":{"value":{"entity-type":"item","numeric-id":598256,"id":"Q598256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$E7B27DF0-FA55-4560-BBC4-5A7CE39A3273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2be8fb6e35685e07f3610c2a477e3fd665571740","datavalue":{"value":{"entity-type":"item","numeric-id":371199,"id":"Q371199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$ACDDA4A9-C9EB-4013-9209-134ACCB6BD50","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$0F03534D-35C7-42DE-BB35-B5AD99D89368","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5e7c33876f49da64580f033b95b71f550b669c2d","datavalue":{"value":{"time":"+2011-12-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5894427$3DB785D3-D3F4-4CA7-894D-8186D2DB432B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9a441ee4de03368a329bc6a6afef2b42009435e0","datavalue":{"value":"A real multivariate polynomial \\(p(x_1, \\ldots , x_n)\\) is said to sign-represent a Boolean function \\(f \\colon \\{0,1\\}^n \\to \\{-1,1\\}\\) if the sign of \\(p(x)\\) equals \\(f(x)\\) for all inputs \\(x \\in \\{0,1\\}^n\\). This paper provides upper and lower bounds on the degree of polynomials which sign-represent Boolean functions.   The upper bounds yield subexponential time learning algorithms for formulas of superconstant depth. The lower bounds for constant-depth circuits and intersections of halfspaces improve results of \\textit{M. Minsky} and \\textit{S. A. Papert} [Perceptrons. expanded ed. London: MIT Press. xvi, 292 p. (1988; Zbl 0794.68104)]. They are proved constructively; explicit dual solutions to the necessary linear programs are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894427$74B62619-FF34-4AC8-8143-97C776139E7E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"278cb718fa512f840b9c5522dfe38ff5e946abf8","datavalue":{"value":{"entity-type":"item","numeric-id":589393,"id":"Q589393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$D7AA7B9E-AE97-4FE5-ACFB-1E67153807FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8de4726dadd4d804f8da0a9b26e1822a2c0c7b53","datavalue":{"value":"05E99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$935A0DBC-F13B-4741-BE04-240334BC387F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"02303c61036060136df3f7b7e22c52163746633f","datavalue":{"value":"68Q99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$7CB064D0-4E74-476E-962D-8249678E3269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$62A2A3C7-D2F5-436B-B29A-1831841418BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c189c45b466f89dd188bd061df8c45f23f05da60","datavalue":{"value":"68Q32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$644BE261-8C52-4B29-AD13-92CD5DF10961","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f72a149603c72cb0c2206f1f1e7bbee645161c18","datavalue":{"value":"5990558","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$92A68E9B-FA7B-4B3D-8A08-078196F5A4F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d53c53856bdf63f3c86f3cff197ae550a3e978af","datavalue":{"value":"polynomial treshold functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894427$B3291652-3EFC-47D1-9740-B2B2AE277BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb5a830579b475e59eaac799be7398a9142f423b","datavalue":{"value":"Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894427$AA5EFB3A-2767-4FE4-81B5-1132E2CDFF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bca5b8f8493e57969b551637f12770d6fc436fb","datavalue":{"value":"learning theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894427$55C7861B-2E0A-46FC-B594-279A90B87DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11acd2fb6ad6c566c252aa4b6fd795400412f6ca","datavalue":{"value":"complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5894427$4C2BFA00-496A-4D26-B2B6-6534787990D8","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":"Q5894427$FBA34C6A-7DB6-4D31-A182-07B252EBCA18","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5db4fb680e6acfc5001c92696bff4e5834f2e035","datavalue":{"value":"https://doi.org/10.1007/s00493-010-2173-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q5894427$609D4345-C5BE-45E1-8DA7-8E4D24D0FF73","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"73c39082652882becbbe5939aca6f93319dad780","datavalue":{"value":"W2610386774","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$64F19D6E-34FF-4A32-9E96-C2EE03C4DACD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf09980eb701e5a3f32afbfa623fd5896cafe9a8","datavalue":{"value":{"entity-type":"item","numeric-id":1330793,"id":"Q1330793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$2373595C-844D-425F-B95A-E71E403A4192","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e992429315736faf25dc16d657c2337beecd29ef","datavalue":{"value":{"entity-type":"item","numeric-id":1346615,"id":"Q1346615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$E6F2306D-E2AC-4484-9AD8-06AE51202D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68616883371a59200cff5f3b736702bbe967345f","datavalue":{"value":{"entity-type":"item","numeric-id":1892214,"id":"Q1892214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$DA0CA3AE-C1F3-444D-95BC-DD4F8E20A86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a88fd98530a92c11c08b418a470b69f2b3f0e11c","datavalue":{"value":{"entity-type":"item","numeric-id":3472059,"id":"Q3472059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$773B079B-66CA-459D-8806-1E88C1FC667D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7643fbbca97bdcb407e7e3e56b1b94a84ce8eb6","datavalue":{"value":{"entity-type":"item","numeric-id":4542521,"id":"Q4542521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$E58CD25F-C884-4DDB-B814-77D60AA4EDBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9872d1e5b694c452e067c737826bed9fab5fdb53","datavalue":{"value":{"entity-type":"item","numeric-id":1853508,"id":"Q1853508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$06C2F8C6-E674-40D9-AFC3-9C586853BF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeb491681eff2d7bbed660d78ab03d245ed96c89","datavalue":{"value":{"entity-type":"item","numeric-id":5543516,"id":"Q5543516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$ED49D81B-EFAA-4D49-90AD-C34456CF48A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2854cda7e5988d324d2751b394a4a2ff4b92b03a","datavalue":{"value":{"entity-type":"item","numeric-id":4769056,"id":"Q4769056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$E3660C60-A486-4357-8423-B71451BB5525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"741bcff6f98953ea09825c9c77020d223f13cfd3","datavalue":{"value":{"entity-type":"item","numeric-id":1899915,"id":"Q1899915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$3CD987EF-3269-4DDF-B13E-17E2764542A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cc5e282c60eae829fadc267b1efccd535e14f0d","datavalue":{"value":{"entity-type":"item","numeric-id":287188,"id":"Q287188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$2C863FA5-F5AA-41F6-A5A0-B0C4009EACB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"258e9e9056926a06af9cec351759111a55665eb1","datavalue":{"value":{"entity-type":"item","numeric-id":2366275,"id":"Q2366275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$A0E4041B-7E97-4347-BBA7-DB5C38601CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a0300aa86dbb0169a9f9102aa818c727feee185","datavalue":{"value":{"entity-type":"item","numeric-id":5175978,"id":"Q5175978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$FFB9DA97-92A7-49F8-AD76-3FC20BACD8DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"296940b22304bf22d40a18b5e0560d47bc035a86","datavalue":{"value":{"entity-type":"item","numeric-id":1293360,"id":"Q1293360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$BA71D249-2D20-4203-AAE0-A42687061B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2daae0bb83cad646c82bd4e30eaf4258cdff2c05","datavalue":{"value":{"entity-type":"item","numeric-id":3140018,"id":"Q3140018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$58FE0731-A178-45E9-9641-19F81E6BC050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c8e0de57dba47aa051a2648724ec7a4688d6486","datavalue":{"value":{"entity-type":"item","numeric-id":5595902,"id":"Q5595902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$6C7B8E41-8D31-4D64-A7B1-E8ED79B5FF4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cab6a3793a6c7638bb44de5f3dc4f6ac6bbe773","datavalue":{"value":{"entity-type":"item","numeric-id":2521832,"id":"Q2521832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$DC3D191C-BB6D-4007-B1A5-2C95BAEB1806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ea7461fbb8956457b11cf96616ab5aebc7c4456","datavalue":{"value":{"entity-type":"item","numeric-id":5901091,"id":"Q5901091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$35578909-79DF-49A5-82F7-C4E0B1F04D6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f0414c19e123f2a2fe555a3a7266f61c87bfe6a","datavalue":{"value":{"entity-type":"item","numeric-id":1333272,"id":"Q1333272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$32B85C3B-10FF-4248-B5AB-8A50933620FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20879ac5473eb95607a44390ce791132728d5d20","datavalue":{"value":{"entity-type":"item","numeric-id":3142416,"id":"Q3142416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$B0865155-E5AB-45B3-80E3-3E0F9CEEE2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c871b2cc321cdb2557f7b2c07a462126294e838b","datavalue":{"value":{"entity-type":"item","numeric-id":2475411,"id":"Q2475411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$9C8D2C28-EBC8-4003-8F5D-9B7A62CD5C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a4339f157b5db47124df1e48c6422ab87d6805d","datavalue":{"value":{"entity-type":"item","numeric-id":3714486,"id":"Q3714486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5894427$5B7A7783-5B90-4C08-8B97-BB99B650C59F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8534799f13ced74cdb3bae713dd0752e7d7949b","datavalue":{"value":"10.1007/S00493-010-2173-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5894427$CD9A5297-7472-468F-AC45-A6C152010259","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7681e076cbc2f083e390c08c62ee0f29ad0136fe","datavalue":{"value":{"entity-type":"item","numeric-id":5901091,"id":"Q5901091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d5a433777e64012baaa75e8a6e03c5dfe8738f4","datavalue":{"value":{"amount":"+0.9731894731521606","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":"Q5894427$386B195A-447F-40BC-991A-2DB8EC13AB29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6f12dd9dcd742f3b51a1be3ea8ce559b21e4d78","datavalue":{"value":{"entity-type":"item","numeric-id":5408769,"id":"Q5408769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0ccadb7874b9b122c4ad062c412c78028dd469b","datavalue":{"value":{"amount":"+0.8376680016517639","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":"Q5894427$7FF94121-AF84-4C0B-82FC-F970389F040E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56d60a4b154ad45a18339a3bffe8d238ad752a61","datavalue":{"value":{"entity-type":"item","numeric-id":2475403,"id":"Q2475403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ee447bc1d1ed9c3da3398b923f308baccd597c7","datavalue":{"value":{"amount":"+0.8323559761047363","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":"Q5894427$8F689816-A189-4122-9756-37D029496275","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5894427","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5894427"}}}}}