All reports by Author Luke Friedman:

__
TR13-027
| 29th January 2013
__

Luke Friedman#### A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques

__
TR13-018
| 29th January 2013
__

Luke Friedman, Yixin Xu#### Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams

__
TR12-054
| 2nd May 2012
__

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff#### Reductions to the set of random strings:the resource-bounded case

Revisions: 1

__
TR12-028
| 30th March 2012
__

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret#### Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

Revisions: 1

__
TR10-139
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Limits on the Computational Power of Random Strings

Revisions: 1

__
TR10-138
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

Luke Friedman

Propositional proof complexity is an area of complexity theory that addresses the question of whether the class NP is closed under complement, and also provides a theoretical framework for studying practical applications such as SAT solving.

Some of the most well-studied contradictions are random $k$-CNF formulas where each clause of ...
more >>>

Luke Friedman, Yixin Xu

A propositional proof system based on ordered binary decision diagrams (OBDDs) was introduced by Atserias et al. Krajicek proved exponential lower bounds for a strong variant of this system using feasible interpolation, and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived ... more >>>

Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $C$ defined ... more >>>

Eric Allender, Luke Friedman, William Gasarch

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

Eric Allender, Luke Friedman, William Gasarch

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>