scientific article; zbMATH DE number 7561750
From MaRDI portal
Publication:5092472
Cites work
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- A threshold of ln n for approximating set cover
- Boolean function complexity. Advances and frontiers.
- Circuit minimization problem
- Communication Complexity
- Communication lower bounds via critical block sensitivity
- Computational limitations on learning from examples
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
- Cryptographic limitations on learning Boolean formulae and finite automata
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Functional decomposition with application to FPGA synthesis
- Graph complexity
- Hardness magnification near state-of-the-art lower bounds
- scientific article; zbMATH DE number 5845490 (Why is no real title available?)
- scientific article; zbMATH DE number 5081744 (Why is no real title available?)
- scientific article; zbMATH DE number 5485546 (Why is no real title available?)
- scientific article; zbMATH DE number 3489106 (Why is no real title available?)
- scientific article; zbMATH DE number 3582190 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1024063 (Why is no real title available?)
- scientific article; zbMATH DE number 1929951 (Why is no real title available?)
- scientific article; zbMATH DE number 795584 (Why is no real title available?)
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- scientific article; zbMATH DE number 5032602 (Why is no real title available?)
- scientific article; zbMATH DE number 3305071 (Why is no real title available?)
- Improper learning by refuting
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Improved hardness of approximating chromatic number
- Learning algorithms from natural proofs
- Limits of minimum circuit size problem as oracle
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Lower bounds on learning decision lists and trees
- Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
- Minimum circuit size, graph isomorphism, and related problems
- Natural proofs
- Non-approximability results for optimization problems on bounded degree instances
- Occam's razor
- On the (non) NP-hardness of computing circuit complexity
- On the average-case complexity of MCSP and its variants
- On the complexity of communication complexity
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- On the hardness of approximating minimization problems
- On the NP-Completeness of the Minimum Circuit Size Problem.
- On the Shortest Linear Straight-Line Program for Computing Linear Forms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The complexity of DNF of parities
- The complexity of properly learning simple concept classes
- The log-approximate-rank conjecture is false
- The minimum oracle circuit size problem
- The non-hardness of approximating circuit size
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Zero knowledge and circuit minimization
- Zero knowledge and the chromatic number
Cited in
(22)- Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Hardness magnification near state-of-the-art lower bounds
- OR-Toffoli and OR-Peres Reversible Gates
- On the NP-Completeness of the Minimum Circuit Size Problem.
- The power of natural properties as oracles
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Constant depth formula and partial function versions of MCSP are hard
- Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
- ESLIM: Circuit minimization with SAT based local improvement
- Gap MCSP is not (Levin) NP-complete in obfustopia
- NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
- Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
- Toward better depth lower bounds: a KRW-like theorem for strong composition
- NP-hardness of approximating meta-complexity: a cryptographic approach
- On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
- Learning algorithms from circuit lower bounds
- An efficient coding theorem via probabilistic representations and its applications
- SAT reduces to the minimum circuit size problem with a random oracle
- Lower bounds on the overhead of indistinguishability obfuscation
- Kolmogorov complexity characterizes statistical zero knowledge
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092472)
