Binary Solutions to Some Systems of Linear Equations

A point is called binary if its coordinates are equal to either zero or one. It is well known that it is hard to find a binary solution to ... Skiptomaincontent Advertisement SearchSpringerLink Search AbstractApointiscalledbinaryifitscoordinatesareequaltoeitherzeroorone.Itiswellknownthatitishardtofindabinarysolutiontothesystemoflinearequationswhosecoefficientsareintegerswithsmallabsolutevalues.Theaimofthearticleistoproposeaneffectiveprobabilisticreductionfromthesystemtotheuniqueequationwhenthereisasmalldifferencebetweenthenumberofbinarysolutionstothefirstequationandthenumberofbinarysolutionstothesystem.Thereexistnontrivialexamplesoflinearequationswithsmallpositivecoefficientshavingasmallnumberofbinarysolutionsinhighdimensions.KeywordsSubsetsumLinearequationProbabilisticalgorithmComputationalcomplexityThisresearchhasbeensupportedbytheRussianScienceFoundation,ProjectNo.14–50–00150. Thisisapreviewofsubscriptioncontent,accessviayourinstitution. Buyingoptions Chapter EUR 29.95 PriceincludesVAT(Singapore) DOI:10.1007/978-3-319-93800-4_15 Chapterlength:10pages InstantPDFdownload Readableonalldevices Ownitforever Exclusiveofferforindividualsonly Taxcalculationwillbefinalisedduringcheckout BuyChapter eBook EUR 64.19 PriceincludesVAT(Singapore) ISBN:978-3-319-93800-4 InstantPDFdownload Readableonalldevices Ownitforever Exclusiveofferforindividualsonly Taxcalculationwillbefinalisedduringcheckout BuyeBook SoftcoverBook EUR 75.99 PriceexcludesVAT(Singapore) ISBN:978-3-319-93799-1 Dispatchedin3to5businessdays Exclusiveofferforindividualsonly FreeshippingworldwideShippingrestrictionsmayapply,checktoseeifyouareimpacted. Taxcalculationwillbefinalisedduringcheckout BuySoftcoverBook Learnaboutinstitutionalsubscriptions ReferencesSchrijver,A.:TheoryofLinearandIntegerProgramming.Wiley,NewYork(1986)MATH  GoogleScholar  Dantzig,G.B.:Discrete-variableextremumproblems.Oper.Res.5(2),266–277(1957)MathSciNet  CrossRef  GoogleScholar  Smolev,V.V.:OnanapproachtothesolutionofaBooleanlinearequationwithpositiveintegercoefficients.DiscreteMath.Appl.3(5),523–530(1993).https://doi.org/10.1515/dma.1993.3.5.523MathSciNet  CrossRef  MATH  GoogleScholar  Tamir,A.:NewpseudopolynomialcomplexityboundsfortheboundedandotherintegerKnapsackrelatedproblems.Oper.Res.Lett.37(5),303–306(2009).https://doi.org/10.1016/j.orl.2009.05.003MathSciNet  CrossRef  MATH  GoogleScholar  Koiliaris,K.,Xu,C.:Afasterpseudopolynomialtimealgorithmforsubsetsum.In:SODA2017ProceedingsoftheTwenty-EighthAnnualACM-SIAMSymposiumonDiscreteAlgorithms,pp.1062–1072.SocietyforIndustrialandAppliedMathematics,Philadelphia(2017) GoogleScholar  Bringmann,K.:Anear-linearpseudopolynomialtimealgorithmforsubsetsum.In:SODA2017ProceedingsoftheTwenty-EighthAnnualACM-SIAMSymposiumonDiscreteAlgorithms,pp.1073–1084.SocietyforIndustrialandAppliedMathematics,Philadelphia(2017) GoogleScholar  Margulies,S.,Onn,S.,Pasechnik,D.V.:OnthecomplexityofHilbertrefutationsforpartition.J.SymbolicComput.66,70–83(2015).https://doi.org/10.1016/j.jsc.2013.06.005MathSciNet  CrossRef  MATH  GoogleScholar  Chistov,A.L.:Animprovementofthecomplexityboundforsolvingsystemsofpolynomialequations.J.Math.Sci.181(6),921–924(2012).https://doi.org/10.1007/s10958-012-0724-4MathSciNet  CrossRef  MATH  GoogleScholar  Jeronimo,G.,Sabia,J.:Sparseresultantsandstraight-lineprograms.J.SymbolicComput.87,14–27(2018).https://doi.org/10.1016/j.jsc.2017.05.005MathSciNet  CrossRef  MATH  GoogleScholar  Latkin,I.V.,Seliverstov,A.V.:Computationalcomplexityoffragmentsofthetheoryofcomplexnumbers.Bull.KaragandaUniv.Math.1,47–55(2015).(InRussian).http://vestnik.ksu.kzSeliverstov,A.V.:Ontangentlinestoaffinehypersurfaces.VestnikUdmurtskogoUniversiteta.Matematika.Mekhanika.Komp’yuternyeNauki27(2),248–256(2017).(InRussian).https://doi.org/10.20537/vm170208MathSciNet  CrossRef  GoogleScholar  Kolokolov,A.A.,Zaozerskaya,L.A.:Findingandanalysisofestimationofthenumberofiterationsinintegerprogrammingalgorithmsusingtheregularpartitioningmethod.RussianMath.(Iz.VUZ)58(1),35–46(2014).https://doi.org/10.3103/S1066369X14010046Håstad,J.,Rossman,B.,Servedio,R.A.,Tan,L.-Y.:Anaverage-casedepthhierarchytheoremforBooleancircuits.J.ACM64(5),35(2017).https://doi.org/10.1145/3095799MathSciNet  CrossRef  GoogleScholar  Horowitz,E.,Sahni,S.:Computingpartitionswithapplicationstotheknapsackproblem.J.ACM21(2),277–292(1974).https://doi.org/10.1145/321812.321823MathSciNet  CrossRef  GoogleScholar  Bansal,N.,Garg,S.,Nederlof,J.,Vyas,N.:Fasterspace-efficientalgorithmsforsubsetsumandk-sum.In:STOC2017Proceedingsofthe49thAnnualACMSIGACTSymposiumonTheoryofComputing,pp.198–209ACM,NewYork(2017).https://doi.org/10.1145/3055399.3055467Lokshtanov,D.,Nederlof,J.:Savingspacebyalgebraization.In:STOC2010ProceedingsoftheForty-secondACMSymposiumonTheoryofComputing,pp.321–330.ACM,NewYork(2010).https://doi.org/10.1145/1806689.1806735Gál,A.,Jang,J.-T.,Limaye,N.,Mahajan,M.,Sreenivasaiah,K.:Space-efficientapproximationsforSubsetSum.ACMTrans.Comput.Theory8(4),16(2016).https://doi.org/10.1145/2894843MathSciNet  CrossRef  GoogleScholar  Williamson,J.:Determinantswhoseelementsare0and1.Am.Math.Monthly53(8),427–434(1946)MathSciNet  CrossRef  GoogleScholar  Alon,N.,Vũ,V.H.:Anti-Hadamardmatrices,coinweighing,thresholdgatesandindecomposablehypergraphs.J.Comb.TheoryA79(1),133–160(1997).https://doi.org/10.1006/jcta.1997.2780MathSciNet  CrossRef  GoogleScholar  Babai,L.,Hansen,K.A.,Podolskii,V.V.,Sun,X.:Weightsofexactthresholdfunctions.In:Hliněný,P.,Kučera,A.(eds.)MFCS2010.LNCS,vol.6281,pp.66–77.Springer,Heidelberg(2010).https://doi.org/10.1007/978-3-642-15155-2_8CrossRef  MATH  GoogleScholar  Gorbunov,K.Yu.,Seliverstov,A.V.,Lyubetsky,V.A.:Geometricrelationshipbetweenparallelhyperplanes,quadrics,andverticesofahypercube.Probl.Inform.Transm.48(2),185–192(2012).https://doi.org/10.1134/S0032946012020081MathSciNet  CrossRef  GoogleScholar  Williams,R.:Newalgorithmsandlowerboundsforcircuitswithlinearthresholdgates.In:STOC2014ProceedingsoftheForty-sixthAnnualACMSymposiumonTheoryofComputing,pp.194–202.ACM,NewYork(2014).https://doi.org/10.1145/2591796.2591858Schwartz,J.T.:Fastprobabilisticalgorithmsforverificationofpolynomialidentities.J.ACM27(4),701–717(1980).https://doi.org/10.1145/322217.322225MathSciNet  CrossRef  GoogleScholar  Bacher,A.,Bodini,O.,Hwang,H.-K.,Tsai,T.-H.:Generatingrandompermutationsbycoin-tossing:classicalalgorithms,newanalysis,andmodernimplementation.ACMTrans.Algorithms13(2),24(2017).https://doi.org/10.1145/3009909Beresnev,V.L.,Melnikov,A.A.:Anupperboundforthecompetitivelocationandcapacitychoiceproblemwithmultipledemandscenarios.J.Appl.Ind.Math.11(4),472–480(2017).https://doi.org/10.1134/S1990478917040020CrossRef  GoogleScholar  DownloadreferencesAcknowledgementsTheauthorwouldliketothanktheanonymousreviewersforusefulcomments.AuthorinformationAuthorsandAffiliationsInstituteforInformationTransmissionProblemsoftheRussianAcademyofSciences(KharkevichInstitute),BolshoyKaretnyper.19,build.1,Moscow,127051,RussiaAlexandrV.SeliverstovAuthorsAlexandrV.SeliverstovViewauthorpublicationsYoucanalsosearchforthisauthorin PubMed GoogleScholarCorrespondingauthorCorrespondenceto AlexandrV.Seliverstov.EditorinformationEditorsandAffiliationsSobolevInstituteofMathematicsSBRAS,Omsk,RussiaDr.AntonEremeevKrasovskyInstituteofMathematicsandMechanics,Ekaterinburg,RussiaMichaelKhachaySobolevInstituteofMathematicsSBRAS,Novosibirsk,RussiaYuryKochetovIndustrialandSystemsEngineering,UniversityofFlorida,Gainesville,Florida,USAProf.PanosPardalosRightsandpermissionsReprintsandPermissionsCopyrightinformation©2018SpringerInternationalPublishingAG,partofSpringerNatureAboutthispaperCitethispaperSeliverstov,A.V.(2018).BinarySolutionstoSomeSystemsofLinearEquations. In:Eremeev,A.,Khachay,M.,Kochetov,Y.,Pardalos,P.(eds)OptimizationProblemsandTheirApplications.OPTA2018.CommunicationsinComputerandInformationScience,vol871.Springer,Cham.https://doi.org/10.1007/978-3-319-93800-4_15Downloadcitation.RIS.ENW.BIBDOI:https://doi.org/10.1007/978-3-319-93800-4_15Published:17June2018 PublisherName:Springer,Cham PrintISBN:978-3-319-93799-1 OnlineISBN:978-3-319-93800-4eBookPackages:ComputerScienceComputerScience(R0)SharethispaperAnyoneyousharethefollowinglinkwithwillbeabletoreadthiscontent:GetshareablelinkSorry,ashareablelinkisnotcurrentlyavailableforthisarticle.Copytoclipboard ProvidedbytheSpringerNatureSharedItcontent-sharinginitiative Accessviayourinstitution Buyingoptions Chapter EUR 29.95 PriceincludesVAT(Singapore) DOI:10.1007/978-3-319-93800-4_15 Chapterlength:10pages InstantPDFdownload Readableonalldevices Ownitforever Exclusiveofferforindividualsonly Taxcalculationwillbefinalisedduringcheckout BuyChapter eBook EUR 64.19 PriceincludesVAT(Singapore) ISBN:978-3-319-93800-4 InstantPDFdownload Readableonalldevices Ownitforever Exclusiveofferforindividualsonly Taxcalculationwillbefinalisedduringcheckout BuyeBook SoftcoverBook EUR 75.99 PriceexcludesVAT(Singapore) ISBN:978-3-319-93799-1 Dispatchedin3to5businessdays Exclusiveofferforindividualsonly FreeshippingworldwideShippingrestrictionsmayapply,checktoseeifyouareimpacted. Taxcalculationwillbefinalisedduringcheckout BuySoftcoverBook Learnaboutinstitutionalsubscriptions