{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:45:52Z","timestamp":1743151552246,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540662242"},{"type":"electronic","value":"9783540485230"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48523-6_15","type":"book-chapter","created":{"date-parts":[[2007,12,10]],"date-time":"2007-12-10T12:06:31Z","timestamp":1197288391000},"page":"179-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs"],"prefix":"10.1007","author":[{"given":"Alexander E.","family":"Andreev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juri L.","family":"Baskakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea E. F.","family":"Clementi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 D. P.","family":"Rolim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,1,18]]},"reference":[{"key":"15_CR1","first-page":"544","volume":"2","author":"N. Alon","year":"1990","unstructured":"N. Alon, O. Goldreich, J. Hastad, and R. Peralta (1990), \u201cSimple Constructions of Almost k-wise Independent Random Variables\u201d, Proc. of IEEE-FOCS, Vol. 2, pp. 544\u2013553.","journal-title":"Proc. of IEEE-FOCS"},{"key":"15_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/3-540-63165-8_175","volume-title":"Proc. of ICALP","author":"A. Andreev","year":"1997","unstructured":"A. Andreev, A. Clementi, and J. Rolim (1997), \u201cWorst-case Hardness Suffices for Derandomization: a New method for Hardness-Randomness Trade-Offs\u201d, in Proc. of ICALP, LNCS, 1256, pp. 177\u2013187 (to appear also on TCS)."},{"key":"15_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BFb0023475","volume-title":"ECCC TR96-029","author":"A. Andreev","year":"1997","unstructured":"A. Andreev, A. Clementi, J. Rolim (1997), \u201cEfficient Constructions of Hitting Sets for Systems of Linear Functions\u201d, in ECCC TR96-029, (Extended Abstract in Proc. of STACS\u201997, LNCS 1200, pp.387\u2013398."},{"key":"15_CR4","unstructured":"A.E. Andreev, J.L. Baskakov, A.E.F. Clementi, J.D.P. Rolim (1997), \u201cSmall Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs\u201d, Electronic Colloquium on Computational Complexity (ECCC), 2nd Revision of TR97-053 (http:\/\/www.eccc.uni-trier.de\/eccc)."},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"R. Armoni, M. Saks, A. Wigderson, and S. Zhou (1996), \u201cDiscrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles\u201d, Proc. of IEEE-FOCS, pp. 412\u2013421.","DOI":"10.1109\/SFCS.1996.548500"},{"issue":"4","key":"15_CR6","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum M., and Micali S. (1984), \u201cHow to generate cryptographically strong sequences of pseudorandom bits\u201d, SIAM J. of Computing, 13(4), pp. 850\u2013864.","journal-title":"SIAM J. of Computing"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"A. Borodin (1993), \u201cTime-Space Trade-Offs (getting closer to the barrier?) \u201d, Proc. of the IV ISAAC, pp. 209\u2013220.","DOI":"10.1007\/3-540-57568-5_251"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"A. Borodin, A. Razborov and R. Smolensky (1993), \u201cOn lower bounds for read-k times branching programs\u201d, Computational Complexity, 3, pp. 1\u201318.","journal-title":"Computational Complexity"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"L. Fortnow (1997), \u201cNondeterministic polynomial time versus nondeterministic logarithmic space: Time-space tradeoffs for satisfiability\u201d, Proc. of 12-th IEEE Conference on Computational Complexity, pp. 52\u201360.","DOI":"10.1109\/CCC.1997.612300"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, and A. Wigderson (1997), \u201cP= BPP if E requires exponential circuits: Derandomizing the XOR lemma\u201d Proc. of ACM STOC, pp. 220\u2013229.","DOI":"10.1145\/258533.258590"},{"issue":"1","key":"15_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1051\/ita\/1995290100751","volume":"29","author":"S. Jukna","year":"1995","unstructured":"S. Jukna (1995), \u201cA Note on Read-k-times Branching programs\u201c, RAIRO Theoretical Informatics and Applications, 29(1), pp.75\u201383. (also in ECCC, TR94-027).","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"15_CR12","unstructured":"Valentine Kabanets (1999), \u201cAlmost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs\u201d, ECCC, TR99-004."},{"issue":"6","key":"15_CR13","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1137\/0222080","volume":"22","author":"E. Kushilevitz","year":"1993","unstructured":"E. Kushilevitz, and Y. Mansour (1993), \u201cLearning Decision Trees Using the Fourier Spectrum\u201d, SICOMP 22(6), pp. 1331\u20131348. Early version: STOC 91.","journal-title":"SICOMP"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"J. Naor, and M. Naor (1990), \u201cSmall-bias probability spaces: efficient constructions and applications\u201d, Proc. of ACM-STOC, pp. 213\u2013223.","DOI":"10.1145\/100216.100244"},{"key":"15_CR15","first-page":"999","volume":"7","author":"E. Neciporuk","year":"1966","unstructured":"E. Neciporuk (1966), \u201cOn a Boolean Function\u201d, Soviet. Math. Doklady, 7, 999\u20131000.","journal-title":"Soviet. Math. Doklady"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan N., and Wigderson A. (1994), \u201cHardness vs Randomness\u201d, J. Comput. System Sci., 49, pp. 149\u2013167.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"15_CR17","first-page":"152","volume":"3","author":"E.A. Okolnishnikova","year":"1993","unstructured":"E.A. Okolnishnikova (1993), \u201cOn lower bounds for branching programs\u201d, Siberian Advances in Mathematics, 3(1), pp. 152\u2013166.","journal-title":"Siberian Advances in Mathematics"},{"key":"15_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Lower Bounds for Deterministic and Nondeterministic Branching Programs","author":"A.A. Razbarov","year":"1991","unstructured":"A.A. Razbarov (1991), \u201cLower Bounds for Deterministic and Nondeterministic Branching Programs\u201d, LNCS, 529, pp. 47\u201361."},{"key":"15_CR19","unstructured":"M. Sauerhoff (1997), \u201cA Lower Bound for Randomized Read-k-Times Branching Programs\u201d, ECCC, TR97-019."},{"key":"15_CR20","unstructured":"P. Savicky and S. Zak (1996), \u201cA large lower bound for 1-branching programs\u201d, ECCC, TR96-036 (Revision 01) (to appear in Theoretical Computer Science)."},{"key":"15_CR21","unstructured":"P. Savicky and S. Zak (1998), \u201cA read-once lower bound and a (1,+k)-hierarchy for branching programs\u201d, (to appear in Theoretical Computer Science)."},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"J. Simon and M. Szegedy (1993), \u201cA new lower bound theorem for read only once branching programs and its applications\u201d, Advances in Computational Complexity Theory (J. Cai, editor), AMS-DIMACS Series, 13, pp.183\u2013193.","DOI":"10.1090\/dimacs\/013\/11"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"I. Wegener (1987), the Complexity of Boolean Functions, B.G. Teubner, 1 edition.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48523-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T03:05:14Z","timestamp":1642820714000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-48523-6_15"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662242","9783540485230"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-48523-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"18 January 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}