No feasible interpolation for TC/sup 0/-Frege proofs
- 23 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual are capacities. Our approach leads to an O(min(n/sup 2/3/, m/sup 1/2/)m log(n/sup 2//m) log U) ...Keywords
This publication has 16 references indexed in Scilit:
- Lower bounds for resolution and cutting plane proofs and monotone computationsThe Journal of Symbolic Logic, 1997
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmeticThe Journal of Symbolic Logic, 1997
- Cutting planes, connectivity, and threshold logicArchive for Mathematical Logic, 1996
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmeticIzvestiya: Mathematics, 1995
- A key distribution system equivalent to factoringJournal of Cryptology, 1988
- The monotone circuit complexity of boolean functionsCombinatorica, 1987
- Tautologies with a unique craig interpolant, uniform vs. nonuniform complexityAnnals of Pure and Applied Logic, 1984
- Constant Depth ReducibilitySIAM Journal on Computing, 1984
- A lower bound for the complexity of Craig's interpolants in sentential logicArchive for Mathematical Logic, 1983
- New directions in cryptographyIEEE Transactions on Information Theory, 1976