Die Graphstruktur boolescher Funktionen

• Applicant: Professor Dr. Georg Schnitger
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 44274447

• Final Report Year: 2010

Final Report Abstract

No abstract available

Publications

• Entropy of operators or why matrix multiplication is hard for small depth circuits, Theory of Comput. Syst., 46(2) (2008), 301–310
  S. Jukna
  
• Expanders and time-restricted branching programs, Theoret. Comput. Sci., 409:3 (2008), 471–476
  S. Jukna
  
• On the hardness of determining small NFA’s and proving lower bounds on their sizes, in: Proc. of 12th Int. Conf. on Developments in Language Theory (DLT 2008, Kyoto, Japan, September 16-19), Lect. Notes in Comput. Sci., Vol. 5257 (2008), pp. 34-55
  J. Hromkovic and G. Schnitger
  
• Very large cliques are easy to detect, Discrete Math. 308(16) (2008), 3717-3721
  A. Andreev and S. Jukna
  
• A nondeterministic space-time tradeoff for linear codes, Inf. Process. Letters 109(5) (2009), 286–289
  S. Jukna
  
• Ambiguity and communication, in: Proc. of 26th Int. Symp. on Aspects of Computer Science (STACS 2009, February 26-28, 2009, Freiburg, Germany), Leibniz International Proceedings in Informatics, Schloss-Dagstuhl, Vol. 3 (2009), pp. 553-564
  J. Hromkovic and G. Schnitger
  
• Lower bounds on the size of sweeping automata, J. Automata, Languages and Combinatorics 14:1 (2009), 23-31
  J. Hromkovic and G. Schnitger
  
• Min-rank conjecture for log-depth circuits, 2010. in: J.Comput. Syst. Sci.
  S. Jukna and G. Schnitger
  
• On covering graphs by complete bipartite subgraphs, Discrete Math. 309(10) (2009), 3399–3403
  S. Jukna and A. Kulikov
  
• On set intersection representations of graphs, J. Graph Theory 61:1 (2009), 55–75
  S. Jukna
  
• On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA’s, Theor. Comput. Sci. 410(30-32) (2009), 2972–2981
  J. Hromkovic, H. Petersen, and G. Schnitger
  
• Circuits with arbitrary gates for random operators, 2010
  S. Jukna and G. Schnitger
  
• On convex complexity measures, Theoret. Comput. Sci., 411(16-18) (2010), 1842–1854
  P. Hrubes, S. Jukna, A. Kulikov, and P. Pudlák
  
• Representing (0,1)-matrices by depth-2 circuits with arbitrary gates, Discrete Math. 310 (2010), 184–187
  S. Jukna