Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples

1. Alekhnovich, M., Braverman, M., Feldman, V., Klivans, A.R., Pitassi, T.: The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. 74(1), 16–34 (2008)

   Article  MathSciNet  MATH  Google Scholar 

2. Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929–965 (1989)

   Article  MathSciNet  MATH  Google Scholar 

3. De, A., Diakonikolas, I., Servedio, R.A.: Learning from satisfying assignments. In: Indyk, P. (ed.) Proc. SODA, pp. 478–497. SIAM, Philadelphia (2015)

   Google Scholar 

4. Dedić, N., Itkis, G., Reyzin, L., Russell, S.: Upper and lower bounds on black-box steganography. J. Cryptology 22(3), 365–394 (2009)

   Article  MathSciNet  MATH  Google Scholar 

5. Flammini, M., Marchetti-Spaccamela, A., Kučera, L.: Learning DNF formulae under classes of probability distributions. In: Proc. COLT, pp. 85–92. ACM, New York (1992)

   Google Scholar 

6. Fridrich, J.: Steganography in digital media: principles, algorithms, and applications. Cambridge University Press, New York (2009)

   Book  MATH  Google Scholar 

7. Hopper, N., von Ahn, L., Langford, J.: Provably secure steganography. IEEE T. Comput. 58(5), 662–676 (2009)

   Article  MathSciNet  MATH  Google Scholar 

8. Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sc. 43, 169–188 (1986)

   Article  MathSciNet  MATH  Google Scholar 

9. Ker, A.D., Bas, P., Böhme, R., Cogranne, R., Craver, S., Filler, T., Fridrich, J., Pevný, T.: Moving steganography and steganalysis from the laboratory into the real world. In: Proc. IH&MMSec, pp. 45–58. ACM, New York (2013)

   Google Scholar 

10. Kodovsky, J., Fridrich, J., Holub, V.: Ensemble classifiers for steganalysis of digital media. IEEE T. Inform. Forensics and Sec. 7(2), 432–444 (2012)

    Article  Google Scholar 

11. Kucera, L., Marchetti-Spaccamela, A., Protasi, M.: On learning monotone DNF formulae under uniform distributions. Inform. Comput. 110(1), 84–95 (1994)

    Article  MathSciNet  MATH  Google Scholar 

12. Liśkiewicz, M., Reischuk, R., Wölfel, U.: Grey-box steganography. Theor. Comput. Sc. 505, 27–41 (2013)

    Article  MathSciNet  MATH  Google Scholar 

13. Natarajan, B.K.: Probably approximate learning of sets and functions. SIAM J. Comput. 20(2), 328–351 (1991)

    Article  MathSciNet  MATH  Google Scholar 

14. Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965–984 (1988)

    Article  MathSciNet  MATH  Google Scholar 

15. Sakai, Y., Maruoka, A.: Learning monotone log-term DNF formulas under the uniform distribution. Theory of Comput. Syst. 33(1), 17–33 (2000)

    Article  MathSciNet  MATH  Google Scholar 

16. Sakai, Y., Maruoka, A.: Learning \(k\)-term monotone boolean formulae. In: Doshita, S., Furukawa, K., Jantke, K.P., Nishida, T. (eds.) ALT 1992. LNCS, vol. 743, pp. 195–207. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

17. Schaathun, H.G.: Machine Learning in Image Steganalysis. Wiley-IEEE Press, Chichester (2012)

    Book  Google Scholar 

18. Valiant, L.G.: A theory of the learnable. CACM 27(11), 1134–1142 (1984)

    Article  MATH  Google Scholar 

19. Verbeurgt, K.: Learning DNF under the uniform distribution in quasi-polynomial time. In: Proc. COLT, pp. 314–326. Morgan Kaufmann Publishers Inc., San Francisco (1990)

    Google Scholar 

Download references