[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
article

Dependent Sets of Constant Weight Binary Vectors

Published: 01 September 1997 Publication History

Abstract

We determine lower bounds for the number of random binary vectors, chosen uniformly from vectors of weight k, needed to obtain a dependent set.

References

[1]
[1] Balakin, G. V., Kolchin, V. F. and Khokhlov, V. I. (1991) Hypercycles in a random hypergraph. Diskretnaya Matematika 3(3) 1-2-108 (in Russian).
[2]
[2] Erdös, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61.
[3]
[3] Kolchin, V. F. and Khokhlov, V. I. (1990) On the number of cycles in a non-equiprobably random graph. Diskretnaya Matematika 2(3) 137-145 (in Russian).

Cited By

View all
  • (2023)Forward Security with Crash Recovery for Secure LogsACM Transactions on Privacy and Security10.1145/363152427:1(1-28)Online publication date: 3-Nov-2023
  • (2018)An exponential lower bound for individualization-refinement algorithms for graph isomorphismProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188900(138-150)Online publication date: 20-Jun-2018
  • (2015)Impact of Redundant Checks on the LP Decoding Thresholds of LDPC CodesIEEE Transactions on Information Theory10.1109/TIT.2015.241752261:5(2240-2255)Online publication date: 1-May-2015
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Combinatorics, Probability and Computing
Combinatorics, Probability and Computing  Volume 6, Issue 3
September 1997
112 pages

Publisher

Cambridge University Press

United States

Publication History

Published: 01 September 1997

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 02 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Forward Security with Crash Recovery for Secure LogsACM Transactions on Privacy and Security10.1145/363152427:1(1-28)Online publication date: 3-Nov-2023
  • (2018)An exponential lower bound for individualization-refinement algorithms for graph isomorphismProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188900(138-150)Online publication date: 20-Jun-2018
  • (2015)Impact of Redundant Checks on the LP Decoding Thresholds of LDPC CodesIEEE Transactions on Information Theory10.1109/TIT.2015.241752261:5(2240-2255)Online publication date: 1-May-2015
  • (2012)Explicit and efficient hash families suffice for cuckoo hashing with a stashProceedings of the 20th Annual European conference on Algorithms10.1007/978-3-642-33090-2_11(108-120)Online publication date: 10-Sep-2012
  • (2010)Tight thresholds for cuckoo hashing via XORSATProceedings of the 37th international colloquium conference on Automata, languages and programming10.5555/1880918.1880943(213-225)Online publication date: 6-Jul-2010
  • (2008)Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract)Proceedings of the 35th international colloquium on Automata, Languages and Programming - Volume Part I10.1007/978-3-540-70575-8_32(385-396)Online publication date: 7-Jul-2008

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media