Danny Harnik
- Aj83.M. AJTAI, E~ Formulae on finite structures, Annals of Pure and Applied Logic 24 (1983), pp. 1-48.Google Scholar
Cross Ref
- AlBaIt86.N. ALON, L. BABAI AND A. ITAI, A fast simple randomized parallel algorithm for the Maximal Independent Set problem, J. of Algorithms 7' (1986), pp. 567-583. Google ScholarDigital Library
- AlBo87.N. ALON AND R. BOPPANA, The monotone circuit complexity of Boolean functions, Combinatorica 7(1) (1987), pp. 1-22. Google ScholarDigital Library
- AmMa96.K. AMANO AND A. MARUOKA, Potential of the approximation method, Proc. of the 37th IEEE Symp. on the Foundations of Computer Science (1996), pp. 431-440. Google ScholarDigital Library
- An85.A. ANDREEV, On a method for obtaining lower bounds for the complexity of individual monotone functions, Dolk. Akad. Nauk. $SSR 282(5) (1985), pp. 1033-1037 (in Russian). English translation in: Soviet Math. Dokl. 31(3) (1985), pp. 530-534.Google Scholar
- BeUl97.C. BERG AND S. ULFBERG, Symmetric approximation arguments for monotone lower bounds without sunflowers, To appear in: Computational Complexity. Google ScholarDigital Library
- BeUlWi99.C. BERG, S. ULFBERG AND A. WIGDER- SON, Manuscript in preparation.Google Scholar
- BoSi90.R. BOPPANA AND M. SIPSER, The complexity of finite functions,in Handbook of Theoretical Computer Science: Volume A Algorithms and Complexity, J. van Leeuwen editor, MIT Press/Elsevier, 1990, pp. 757-804. Google ScholarDigital Library
- EGLNV92.G. EVEN, O. GOLDREICH, M. LUBY, N. NISAN AND B. VELICKOVIC, Approximations of general independent distributions, Proc. of the 2Jth A CM Syrup. on the Theory of Computing (1992), pp. 10-16. Google ScholarDigital Library
- FuSaSi81.M. FURST, J. SAXE AND M. $IPSER, Parity, circuits and the polynomial time hierarchy, Proc. of the 22th IEEE Symp. on the Foundations of Computer Science (1981), pp. 260-270.Google Scholar
- Ha86.J. HASTAD, Almost optimal lower bounds for small depth circuits, Proc. of the 18th A CM $ymp. on the Theory of Computing (1986), pp. 6-20. Also in Randomness and Computation, Advances in Computing Research, Vol 5, ed. S. Micali, JAI Press Inc (1989), pp. 143-170. Google ScholarDigital Library
- Ha95.A. HAKEN, Counting bottlenecks to show monotone P~:NP, Proc. of the 36th IEEE Syrup. on the Foundations of Computer Science (1995), pp. 36- 40. Google ScholarDigital Library
- Ju97.$. JUKNA, Finite limits and monotone computations: the lower bound criterion, Proc. of the 12th IEEE Conference on Computational Complexity (1997), pp. 302-312. Google ScholarDigital Library
- Pu97.P. PUDLAK, Lower bounds for resolution and cutting planes proofs and monotone computation, The Journal of Symbolic Logic, 62(3) (1997), pp. 981-998.Google ScholarCross Ref
- Ra85.A. RAZBOROV, Lower bounds on the monotone complexity of some Boolean function, Dolk. Akad. Nauk. SSSR 281(4) (1985), 598-607 (in Russian). English translation in: Soviet Math. Dokl. 31 (1985), 354-357.Google Scholar
- Ra89.A. RAZBOROV, On the method of approximation, Proc. of the 21th ACM Syrup. on the Theory of Computing (1989), pp. 167-176. Google ScholarDigital Library
- SiTs97.J. SIMON AND S.C. TSAI, A note on the bottleneck counting argument, In 12th Annual IEEE Conference on Computational Complexity (1997). Google ScholarDigital Library
- Ya85.A. YAO, Separating the polynomial-time hierarchy by oracles, Proc. of the 26th IEEE Symp. on the Foundations of Computer Science (1985), pp. 1-10. Google ScholarDigital Library
Index Terms
- Higher lower bounds on monotone size
Recommendations
Error bounds for nondegenerate monotone linear complementarity problems
Error bounds and upper Lipschitz continuity results are given for monotone linear complementarity problems with a nondegenerate solution. The existence of a nondegenerate solution considerably simplifies the error bounds compared with problems for which ...
Error Bounds for Lower Semicontinuous Functions in Normed Spaces
Without the convexity or analyticity assumption, we study error bounds for an inequality system defined by a general lower semicontinuous function and establish sufficient/necessary conditions on the existence of error bounds in infinite dimensional ...
Some Bounds on the Size of Codes
We present some upper bounds on the size of nonlinear codes and their restriction to systematic codes and linear codes. These bounds are independent of other known theoretical bounds, e.g., the Griesmer bound, the Johnson bound, the Plotkin bound, and ...
Comments