A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms

No abstract is available for this paper.

• Publication year

  1984

• Venue

  Annals of the History of Computing

• Publication date

  1984-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/MAHC.1984.10036
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Structure of Sets in NP and Other Complexity Classes

  1981cited by this paper
• Independence Results in Computer Science?

  1981cited by this paper
• Polynomial algorithms in linear programming

  1980cited by this paper
• A Logical Approach to the Problem "P=NP?"

  1980influential reference
• The consistency of "P = NP" and related problems with fragments of number theory

  1980cited by this paper
• Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

  1980cited by this paper
• A polynomial algorithm in linear programming

  1979cited by this paper
• Observations about the development of theoretical computer science

  1979cited by this paper
• Frequency Algorithms and Computations

  1977cited by this paper
• Relativizations of the P =? NP Question

  1975cited by this paper
• On Problems Solvable by Successive Trials

  1975influential reference
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

  1975cited by this paper
• Formalization of Some Notions in Terms of Computational Complexity

  1973cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper
• COMPUTATIONALLY COMPLEX AND PSEUDO-RANDOM ZERO-ONE VALUED FUNCTIONS††Portions of this work were carried out at Carngie-Mellon University, while the authors were in the Department of Computer Science. Portions of these results were reported in preliminary form in [1].

  1971cited by this paper
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

  1970cited by this paper
• Computability by Probabilistic Machines

  1970cited by this paper
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

  1970cited by this paper
• Synthesis of Switching Circuits

  1968cited by this paper
• NORMAL ALGORITHMS CONNECTED WITH THE COMPUTATION OF BOOLEAN FUNCTIONS

  1967cited by this paper
• On the Length of Programs for Computing Finite Binary Sequences

  1966cited by this paper
• A Formal Theory of Inductive Inference. Part II

  1964cited by this paper
• The Theory of Automata, a Survey

  1961cited by this paper
• Degree of difficulty of computing a function and a partial ordering of recursive sets

  1960cited by this paper
• January

  1890cited by this paper

• An invitation to "Fine-grained complexity of NP -complete problems"

  2026cites this paper
• An Invitation to "Fine-grained Complexity of NP-Complete Problems"

  2026cites this paper
• Hardness Along the Boundary: Towards One-Way Functions from the Worst-Case Hardness of Time-Bounded Kolmogorov Complexity

  2025cites this paper
• Artificial Intelligence and Inherent Mathematical Difficulty

  2025cites this paper
• Sustainable Design: Minimizing Discomfort Glare Through Data-Driven Methods for Responsive Facades

  2025cites this paper
• Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets

  2025cites this paper
• One-way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity

  2025cites this paper
• Simple general magnification of circuit lower bounds

  2025cites this paper
• Guest Column: On Cryptography and Meta-Complexity

  2025cites this paper
• Simple Circuit Extensions for XOR in PTIME

  2025cites this paper
• Hybrid classical and quantum-inspired features framework for MAX-3-SAT difficulty classification using machine learning

  2025cites this paper
• FedSAT-Detect: A Federated Learning Framework for Privacy-Preserving Cybersecurity Threat Detection in Cloud Systems

  2025cites this paper
• A Note on Avoid vs MCSP

  2025cites this paper
• On Black-Box Meta Complexity and Function Inversion

  2024cites this paper
• The PRODSAT phase of random quantum satisfiability

  2024cites this paper
• Levin-Kolmogorov Complexity is not in Linear Time

  2024influential citation
• Lower Bounds for Levin-Kolmogorov Complexity

  2024cites this paper
• Search-to-Decision Reductions for Kolmogorov Complexity

  2024cites this paper
• A Direct PRF Construction from Kolmogorov Complexity

  2024influential citation
• Gap MCSP is not (Levin) NP-complete in Obfustopia

  2024cites this paper
• Network topology and interaction logic determine states it supports

  2024cites this paper
• Beating Brute Force for Compression Problems

  2024cites this paper
• Artifical intelligence and inherent mathematical difficulty

  2024influential citation
• Cross-modal similar clinical case retrieval using a modular model based on contrastive learning and k-nearest neighbor search

  2024cites this paper
• Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

  2024cites this paper
• Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

  2024cites this paper
• Data Reconstruction: When You See It and When You Don't

  2024cites this paper
• SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

  2023cites this paper
• Toward Basing Cryptography on the Hardness of EXP

  2023cites this paper
• Symbolic Execution of Hadamard-Toffoli Quantum Circuits

  2023cites this paper
• NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

  2023cites this paper
• Enhanced Hybrid Energy-Efficient Distributed Clustering Protocol for IoT-Based WSNs with Multiple Sinks

  2023cites this paper
• Research on An Active Zoning Strategy of Regional Grid under Power Grid Attacks

  2023cites this paper
• Vector Databases and Vector Embeddings-Review

  2023cites this paper
• Characterizing the Power of (Persistent) Randomness in Log-space

  2023cites this paper
• Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

  2023cites this paper
• On One-Way Functions and Sparse Languages

  2023cites this paper
• A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers

  2023influential citation
• One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

  2023cites this paper
• On Representation Complexity of Model-based and Model-free Reinforcement Learning

  2023cites this paper
• On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

  2023influential citation
• Synergy Between Circuit Obfuscation and Circuit Minimization

  2023cites this paper
• Proximity to Losslessly Compressible Parameters

  2023cites this paper
• Quantum circuit unoptimization

  2023cites this paper
• Characterizing derandomization through hardness of Levin-Kolmogorov complexity

  2022influential citation
• The Minimum Formula Size Problem is (ETH) Hard

  2022cites this paper
• Retrodictive Quantum Computing

  2022cites this paper
• On the Controllability of Artificial Intelligence: An Analysis of Limitations

  2022cites this paper
• Efficient Cable Path Optimization Based on Critical Robot Poses for Industrial Robot Arms

  2022cites this paper
• An Axiomatic and Computational Analysis of Altruism, Fairness, and Stability in Coalition Formation Games

  2022cites this paper
• Boris Abramovich Trakhtenbrot

  2022cites this paper
• Robustness of average-case meta-complexity via pseudorandomness

  2022cites this paper
• Revisiting Maximum Satisfiability and Related Problems in Data Streams

  2022cites this paper
• Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization

  2022cites this paper
• A historical note on the complexity of scheduling problems

  2022cites this paper
• On one-way functions from NP-complete problems

  2022cites this paper
• How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?

  2022cites this paper
• NP-Hardness of Learning Programs and Partial MCSP

  2022cites this paper
• Symmetry of information from meta-complexity

  2022cites this paper
• Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

  2021cites this paper
• Lifting for Constant-Depth Circuits and Applications to MCSP

  2021cites this paper
• Withdrawn: A Measurement-based Algorithm for Graph Colouring

  2021cites this paper
• Algebraic Geometry and Representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science

  2021cites this paper
• Fifty years of P vs. NP and the possibility of the impossible

  2021cites this paper
• Hardness of KT characterizes parallel cryptography

  2021cites this paper
• A Relativization Perspective on Meta-Complexity

  2021cites this paper
• Perfect Tabular Hashing in Pseudolinear Time

  2021cites this paper
• Quantum Meets the Minimum Circuit Size Problem

  2021cites this paper
• Practical Full Chip Clock Distribution Design With a Flexible Topology and Hybrid Metaheuristic Technique

  2021cites this paper
• On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

  2021cites this paper
• Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity

  2021cites this paper
• A Measurement-based Algorithm for Graph Colouring

  2021cites this paper
• CMSC 858M: Algorithmic Lower Bounds: Fun with Hardness Proofs

  2021cites this paper
• Hardness of constant-round communication complexity

  2021cites this paper
• Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines

  2021cites this paper
• Guest Column

  2021cites this paper
• Learning from the Past - Do Historical Data Help to Improve Progress Indicators in Web Surveys?

  2020cites this paper
• On One-way Functions and Kolmogorov Complexity

  2020influential citation
• On Controllability of AI

  2020cites this paper
• On the Theory of Modern Quantum Algorithms

  2020cites this paper
• Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

  2020cites this paper
• Energy Harvesting Enabled Energy Efficient Cognitive Machine-to-Machine Communications

  2020cites this paper
• Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]

  2020cites this paper
• The importance of the spectral gap in estimating ground-state energies

  2020cites this paper
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem

  2020cites this paper
• Sharp threshold results for computational complexity

  2020cites this paper
• Circuit lower bounds from NP-hardness of MCSP under turing reductions

  2020cites this paper
• A Polynomial-Time Algorithm for Optimization of Quadratic Pseudo-Boolean Functions

  2020cites this paper
• Connecting perebor conjectures: search to decision reduction for formulas

  2020influential citation
• Dise\~no e implementaci\'on de una meta-heur\'istica multi-poblacional de optimizaci\'on combinatoria enfocada a la resoluci\'on de problemas de asignaci\'on de rutas a veh\'iculos

  2020cites this paper
• Improving WalkSAT for Random 3-SAT Problems

  2020cites this paper
• Constant Depth Formula and Partial Function Versions of MCSP are Hard

  2020cites this paper
• A Profit-maximizing Mechanism for Query-based Data Trading with Personalized Differential Privacy

  2020cites this paper
• Tensor Network Rewriting Strategies for Satisfiability and Counting

  2020cites this paper
• NP-hardness of circuit minimization for multi-output functions

  2020cites this paper
• Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions

  2020cites this paper
• Fundamentals of Computing

  2020cites this paper
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

  2020cites this paper
• Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

  2020cites this paper
• Cross Site Scripting Vulnerabilities in JAX-RS: A Security Approach

  2019cites this paper