vix.ing · top · new · best · stats · spec

Golovnev, Alexander

  1. Breaking the encryption scheme of the Moscow Internet voting system
    2019/08/14 by Pierrick Gaudry, Gaudry, Pierrick, Alexander Golovnev +1 · 4 voices
    #cs.CR
  2. Linear Space Streaming Lower Bounds for Approximating CSPs
    2021/06/24 by Chi-Ning Chou, Alexander Golovnev, Chou, Chi-Ning +7 · 6 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  3. Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT
    2020/04/24 by Chi-Ning Chou, Alexander Golovnev, Chou, Chi-Ning +3 · 5 citations
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems
  4. Sketching approximability of all finite CSPs
    2021/05/03 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +5 · 5 citations
    Computer Science · Engineering · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Machine Learning and Algorithms #Scheduling and Optimization Algorithms
  5. Tight Lower Bounds on Graph Embedding Problems
    2016/02/16 by Cygan, Marek, Fomin, Fedor V., Golovnev, Alexander +4 · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  6. The Minrank of Random Graphs
    2016/07/17 by Golovnev, Alexander, Regev, Oded, Weinstein, Omri · 2 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
  7. Sketching Approximability of (Weak) Monarchy Predicates
    2022/05/04 by Chou, Chi-Ning, Golovnev, Alexander, Shahrasbi, Amirbehshad +2 · 3 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  8. Circuit Depth Reductions
    2018/11/12 by Alexander Golovnev, Alexander S. Kulikov, Golovnev, Alexander +3 · 2 citations
    Computer Science · #Advanced Graph Theory Research #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  9. Quantum Worst-Case to Average-Case Reductions for All Linear Problems
    2022/12/06 by Asadi, Vahid R., Golovnev, Alexander, Gur, Tom +2 · 3 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
  10. Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
    2023/03/09 by Gajulapalli, Karthik, Golovnev, Alexander, Nagargoje, Satyajeet +1 · 4 citations
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  11. The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
    2020/02/20 by Golovnev, Alexander, Haviv, Ishay · 2 citations
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
  12. Lower Bounds for the Graph Homomorphism Problem
    2015/02/19 by Fedor V. Fomin, Alexander Golovnev, Fomin, Fedor V. +5 · 1 citation
    Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  13. Collapsing Superstring Conjecture
    2018/09/23 by Golovnev, Alexander, Kulikov, Alexander S., Logunov, Alexander +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  14. Static Data Structure Lower Bounds Imply Rigidity
    2018/11/07 by Dvir, Zeev, Golovnev, Alexander, Weinstein, Omri · 1 citation
    #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
  15. The information-theoretic value of unlabeled data in semi-supervised learning
    2019/01/16 by Alexander Golovnev, Dávid Pál, Golovnev, Alexander +3 · 1 citation
    Computer Science · #Algorithms and Data Compression #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification
  16. Approximability of all Boolean CSPs with linear sketches
    2021/02/24 by Chi-Ning Chou, Chou, Chi-Ning, Alexander Golovnev +5 · 2 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #semigroups and automata theory
  17. Derandomization of Cell Sampling
    2021/08/12 by Alexander Golovnev, Golovnev, Alexander, Tom Gur +3 · 1 citation
    Biochemistry, Genetics and Molecular Biology · #Cell Image Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  18. Worst-Case to Average-Case Reductions via Additive Combinatorics
    2022/02/18 by Asadi, Vahid R., Golovnev, Alexander, Gur, Tom +1 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  19. Polynomial formulations as a barrier for reduction-based hardness proofs
    2022/05/16 by Belova, Tatiana, Golovnev, Alexander, Kulikov, Alexander S. +2 · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences