Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link
11	Arturo I. Merino, Namrata, Aaron Williams	On the Hardness of Gray Code Problems for Combinatorial Objects.	CoRR	2024	DBLP DOI BibTeX RDF
11	Ilan Doron Arad, Guy Kortsarz, Joseph Naor, Baruch Schieber, Hadas Shachnai	Approximations and Hardness of Packing Partially Ordered Items.	CoRR	2024	DBLP DOI BibTeX RDF
11	Bobak T. Kiani, Thien Le, Hannah Lawrence, Stefanie Jegelka, Melanie Weber 0001	On the hardness of learning under symmetries.	CoRR	2024	DBLP DOI BibTeX RDF
11	Zack Fitzsimmons, Vignesh Viswanathan, Yair Zick	On the Hardness of Fair Allocation under Ternary Valuations.	CoRR	2024	DBLP DOI BibTeX RDF
11	Venkatesan Guruswami, Rishi Saket	Hardness of Learning Boolean Functions from Label Proportions.	CoRR	2024	DBLP DOI BibTeX RDF
11	Helena Bergold, Manfred Scheucher, Felix Schröder	Finding hardness reductions automatically using SAT solvers.	CoRR	2024	DBLP DOI BibTeX RDF
11	Shuichi Hirahara, Naoto Ohsaka	Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration.	CoRR	2024	DBLP DOI BibTeX RDF
11	Leroy Chew, Alexis de Colnet, Friedrich Slivovsky, Stefan Szeider	Hardness of Random Reordered Encodings of Parity for Resolution and CDCL.	CoRR	2024	DBLP DOI BibTeX RDF
11	Dhanyamol Antony, Anita Das 0001, Shirish Gosavi, Dalu Jacob, Shashanka Kulamarva	Graph Burning: Bounds and Hardness.	CoRR	2024	DBLP DOI BibTeX RDF
11	Baris Can Esmer, Jacob Focke, Dániel Marx, Pawel Rzazewski	Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness.	CoRR	2024	DBLP DOI BibTeX RDF
11	Hans L. Bodlaender, Krisztina Szilágyi	XNLP-hardness of Parameterized Problems on Planar Graphs.	CoRR	2024	DBLP DOI BibTeX RDF
11	M. A. Shalu, Cyriac Antony	Hardness transitions and uniqueness of acyclic colouring.	Discret. Appl. Math.	2024	DBLP DOI BibTeX RDF
11	Mehri Momeni, Marziyeh Afkanpour, Saleh Rakhshani, Amin Mehrabian, Hamed Tabesh	A prediction model based on artificial intelligence techniques for disintegration time and hardness of fast disintegrating tablets in pre-formulation tests.	BMC Medical Informatics Decis. Mak.	2024	DBLP DOI BibTeX RDF
11	Amir Mahdi Sadeghzadeh, Amir Mohammad Sobhanian, Faezeh Dehghan, Rasool Jalili	HODA: Hardness-Oriented Detection of Model Extraction Attacks.	IEEE Trans. Inf. Forensics Secur.	2024	DBLP DOI BibTeX RDF
11	Wenwen Xia, Leizhang Wang, Geng Wang, Dawu Gu, Baocang Wang	A Refined Hardness Estimation of LWE in Two-step Mode.	IACR Cryptol. ePrint Arch.	2024	DBLP BibTeX RDF
11	Divesh Aggarwal, Leong Jin Ming, Alexandra Veliche	Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective.	IACR Cryptol. ePrint Arch.	2024	DBLP BibTeX RDF
11	Xianxian Wang, Yanchao Cai, Xiucheng Liu, Cunfu He	Quantitative Prediction of Surface Hardness in Cr12MoV Steel and S136 Steel with Two Magnetic Barkhausen Noise Feature Extraction Methods.	Sensors	2024	DBLP DOI BibTeX RDF
11	Redent Tonna, Panagiotis E. Chatzistergos, Otis Wyatt, Nachiappan Chockalingam	Reliability and Validity of Shore Hardness in Plantar Soft Tissue Biomechanics.	Sensors	2024	DBLP DOI BibTeX RDF
11	Masamune Waga, Toru Matsubara, Masashi Konyo, Toshihiro Takeshita, Yusuke Takei, Takeshi Kobayashi, Satoshi Tadokoro	Representing Fine Texture of Pencil Hardness by High-Frequency Vibrotactile Equivalence Conversion Using Ultra-Thin PZT-MEMS Vibrators.	IEEE Trans. Haptics	2024	DBLP DOI BibTeX RDF
11	David Gamarnik, Aukosh Jagannath, Alexander S. Wein	Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics.	SIAM J. Comput.	2024	DBLP DOI BibTeX RDF
11	Will Perkins 0001, Yuzhou Wang	On the hardness of finding balanced independent sets in random bipartite graphs.	SODA	2024	DBLP DOI BibTeX RDF
11	Tuukka Korhonen, Daniel Lokshtanov	Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition.	SODA	2024	DBLP DOI BibTeX RDF
11	Peter Bürgisser, Gorav Jindal	On the Hardness of PosSLP.	SODA	2024	DBLP DOI BibTeX RDF
11	Radu Curticapean	Count on CFI graphs for #P-hardness.	SODA	2024	DBLP DOI BibTeX RDF
11	Arturo I. Merino, Namrata, Aaron Williams	On the Hardness of Gray Code Problems for Combinatorial Objects.	WALCOM	2024	DBLP DOI BibTeX RDF
11	Euiwoong Lee, Pasin Manurangsi	Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs.	ITCS	2024	DBLP DOI BibTeX RDF
11	Nick Fischer, Piotr Kaliciak, Adam Polak 0001	Deterministic 3SUM-Hardness.	ITCS	2024	DBLP DOI BibTeX RDF
11	Martin Avanzini, Georg Moser, Romain Péchoux, Simon Perdrix	On the Hardness of Analyzing Quantum Programs Quantitatively.	ESOP (2)	2024	DBLP DOI BibTeX RDF
11	Markus Hecher, Rafael Kiesel	On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions?	AAAI	2024	DBLP DOI BibTeX RDF
11	Hao-Kai Zhang, Chengkai Zhu, Geng Liu, Xin Wang	Exponential Hardness of Optimization from the Locality in Quantum Neural Networks.	AAAI	2024	DBLP DOI BibTeX RDF
11	Riwei Lai, Rui Chen 0012, Qilong Han, Chi Zhang 0060, Li Chen 0009	Adaptive Hardness Negative Sampling for Collaborative Filtering.	AAAI	2024	DBLP DOI BibTeX RDF
11	Aritra Konar, Nicholas D. Sidiropoulos	Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining.	AAAI	2024	DBLP DOI BibTeX RDF
11	Ziqian Zeng, Yihuai Hong, Hongliang Dai, Huiping Zhuang, Cen Chen	ConsistentEE: A Consistent and Hardness-Guided Early Exiting Method for Accelerating Language Models Inference.	AAAI	2024	DBLP DOI BibTeX RDF
11	Leroy Chew, Alexis de Colnet, Friedrich Slivovsky, Stefan Szeider	Hardness of Random Reordered Encodings of Parity for Resolution and CDCL.	AAAI	2024	DBLP DOI BibTeX RDF
11	Simon Dold, Malte Helmert	Novelty vs. Potential Heuristics: A Comparison of Hardness Measures for Satisficing Planning.	AAAI	2024	DBLP DOI BibTeX RDF
11	Wenwen Xia, Leizhang Wang, Geng Wang, Dawu Gu, Baocang Wang	A Refined Hardness Estimation of LWE in Two-Step Mode.	Public Key Cryptography (3)	2024	DBLP DOI BibTeX RDF
11	Zhedong Wang, Qiqi Lai, Feng-Hao Liu	Ring/Module Learning with Errors Under Linear Leakage - Hardness and Applications.	Public Key Cryptography (2)	2024	DBLP DOI BibTeX RDF
11	Thore Gerlach, Sascha Mücke	Investigating the Relation Between Problem Hardness and QUBO Properties.	IDA (2)	2024	DBLP DOI BibTeX RDF
11	Hanlin Liu, Xiao Wang 0012, Kang Yang 0002, Yu Yu 0001	The Hardness of LPN over Any Integer Ring and Field for PCG Applications.	EUROCRYPT (6)	2024	DBLP DOI BibTeX RDF
11	Marek Filakovský, Tamio-Vesa Nakajima, Jakub Oprsal, Gianluca Tasinato, Uli Wagner 0001	Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.	STACS	2024	DBLP DOI BibTeX RDF
11	Diego Maldonado, Pedro Montealegre 0001, Martín Ríos Wilson	The Hardness of Local Certification of Finite-State Dynamics.	LATIN (1)	2024	DBLP DOI BibTeX RDF
11	Dhanyamol Antony, L. Sunil Chandran, Ankit Gayen, Shirish Gosavi, Dalu Jacob	Total Domination, Separated-Cluster, CD-Coloring: Algorithms and Hardness.	LATIN (1)	2024	DBLP DOI BibTeX RDF
11	Jean-François Biasse, Xavier Bonnetain, Elena Kirshanova, André Schrottenloher, Fang Song 0001	Quantum algorithms for attacking hardness assumptions in classical and post-quantum cryptography.	IET Inf. Secur.	2023	DBLP DOI BibTeX RDF
11	Xiaofang Zhao, Faming Li, Biao Chen, Xiaofei Li, Shasha Lu	Modeling the hardness properties of high-performance concrete via developed RBFNN coupling matheuristic algorithms.	J. Intell. Fuzzy Syst.	2023	DBLP DOI BibTeX RDF
11	Chuncha Wang	Developing support vector regression and radial basis function neural networks in optimized holistic frameworks to estimate hardness properties of concrete.	J. Intell. Fuzzy Syst.	2023	DBLP DOI BibTeX RDF
11	Alessandro Barenghi, Jean-François Biasse, Edoardo Persichetti, Paolo Santini	On the computational hardness of the code equivalence problem in cryptography.	Adv. Math. Commun.	2023	DBLP DOI BibTeX RDF
11	Bao Zhu, Hanwen Yu, Yang Lan, Yong Wang 0011	Weak NP-Hardness for the 2-D L0-Norm InSAR Phase Unwrapping.	IEEE Geosci. Remote. Sens. Lett.	2023	DBLP DOI BibTeX RDF
11	Tim Zeitz	NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times.	Inf. Process. Lett.	2023	DBLP DOI BibTeX RDF
11	Euiwoong Lee, Pengxiang Wang 0002	Strong hardness of approximation for tree transversals.	Inf. Process. Lett.	2023	DBLP DOI BibTeX RDF
11	Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl	Hardness Characterisations and Size-width Lower Bounds for QBF Resolution.	ACM Trans. Comput. Log.	2023	DBLP DOI BibTeX RDF
11	Katarína Cechlárová, Julien Lesca, Diana Trellová, Martina Hancová, Jozef Hanc	Hardness of candidate nomination.	Auton. Agents Multi Agent Syst.	2023	DBLP DOI BibTeX RDF
11	Paulo R. G. Cordeiro, George D. C. Cavalcanti, Rafael M. O. Cruz	Dynamic Ensemble Algorithm Post-Selection Using Hardness-Aware Oracle.	IEEE Access	2023	DBLP DOI BibTeX RDF
11	Jingwei Sha, Mengbao Fan, Binghua Cao, Bo Ye	Deep Transfer Learning-Enabled Hardness Classification of Bearing Rings Using Pulsed Eddy Current Testing.	IEEE Trans. Instrum. Meas.	2023	DBLP DOI BibTeX RDF
11	Chenglin Cai, Zexian Li, Feng Yin, Zhong Wang, Yangzhuo Chen	Automatic Vickers Hardness Measurement With Neural Network Segmentation.	IEEE Trans. Instrum. Meas.	2023	DBLP DOI BibTeX RDF
11	Karthik C. S., Parinya Chalermsook, Joachim Spoerhase, Meirav Zehavi, Martin Herold	Parameterized Approximation: Algorithms and Hardness (Dagstuhl Seminar 23291).	Dagstuhl Reports	2023	DBLP DOI BibTeX RDF
11	Jibo Bai, Baojiang Li, Haiyan Wang 0013, Yutin Guo	A CNN-LSTM model for the effects of object temperature, object hardness, and grip strength on human sensation grasped by a prosthetic hand.	Multim. Tools Appl.	2023	DBLP DOI BibTeX RDF
11	Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen	On the Hardness of Module Learning with Errors with Short Distributions.	J. Cryptol.	2023	DBLP DOI BibTeX RDF
11	Michael Skotnica, Martin Tancer	NP-Hardness of Computing PL Geometric Category in Dimension 2.	SIAM J. Discret. Math.	2023	DBLP DOI BibTeX RDF
11	Dror Chawin, Ishay Haviv	Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank.	SIAM J. Discret. Math.	2023	DBLP DOI BibTeX RDF
11	Yunona Iwasaki, Ching-Yao Lai	One-dimensional ice shelf hardness inversion: Clustering behavior and collocation resampling in physics-informed neural networks.	J. Comput. Phys.	2023	DBLP DOI BibTeX RDF
11	Qi Jiang, Jialiang Yan	Shape and Hardness Perception of Robot Soft Finger Based on Fiber Bragg Grating.	IEEE Instrum. Meas. Mag.	2023	DBLP DOI BibTeX RDF
11	Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle	Cryptographic hardness under projections for time-bounded Kolmogorov complexity.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
11	Andrea Caucchiolo, Ferdinando Cicalese	Hardness and approximation of multiple sequence alignment with column score.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
11	Renzo Gómez, Flávio Keidi Miyazawa, Yoshiko Wakabayashi	Improved NP-hardness results for the minimum t-spanner problem on bounded-degree graphs.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
11	Dirk Briskorn, Gerhard J. Woeginger	Hardness of flow time minimization in a crossdock with a single door and asymmetric handover relations.	Oper. Res. Lett.	2023	DBLP DOI BibTeX RDF
11	Leonid Barenboim, Harel Levin	Secured distributed algorithms without hardness assumptions.	J. Parallel Distributed Comput.	2023	DBLP DOI BibTeX RDF
11	Yilei Chen, Jiatu Li	Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Yanyi Liu, Rafael Pass	One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Sagnik Saha, Nikolaj I. Schwartzbach, Prashant Nalini Vasudevan	The Planted $k$-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Benny Applebaum, Oded Nir	Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Edward Pyne, Ran Raz, Wei Zhan	Certified Hardness vs. Randomness for Log-Space.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Yanyi Liu, Rafael Pass	On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi	Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Nicollas M. Sdroievski, Dieter van Melkebeek	Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov 0001	Hardness Condensation by Restriction.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Shuichi Hirahara, Nobutaka Shimizu	Hardness Self-Amplification: Simplified, Optimized, and Unified.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Xin Li 0006, Yan Zhong 0002	Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Shuichi Hirahara	Capturing One-Way Functions via NP-Hardness of Meta-Complexity.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	William Hoza	A Technique for Hardness Amplification Against $\mathrm{AC}^0$.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Yizhi Huang, Rahul Ilango, Hanlin Ren	NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Dean Doron, Edward Pyne, Roei Tell	Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai	Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
11	Quoc-Tung Le, Elisa Riccietti, Rémi Gribonval	Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support.	SIAM J. Matrix Anal. Appl.	2023	DBLP DOI BibTeX RDF
11	Upendra Kapshikar, Srijita Kundu	On the Hardness of the Minimum Distance Problem of Quantum Codes.	IEEE Trans. Inf. Theory	2023	DBLP DOI BibTeX RDF
11	Giulia Bernardini 0001, Alessio Conte, Garance Gourdel, Roberto Grossi, Grigorios Loukides, Nadia Pisanti, Solon P. Pissis, Giulia Punzi, Leen Stougie, Michelle Sweering	Hide and Mine in Strings: Hardness, Algorithms, and Experiments.	IEEE Trans. Knowl. Data Eng.	2023	DBLP DOI BibTeX RDF
11	Marek Filakovský, Tamio-Vesa Nakajima, Jakub Oprsal, Gianluca Tasinato, Uli Wagner 0001	Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Dror Chawin, Ishay Haviv	Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank.	CoRR	2023	DBLP DOI BibTeX RDF
11	Yakov Shalunov	Leakage-Resilient Hardness Equivalence to Logspace Derandomization.	CoRR	2023	DBLP DOI BibTeX RDF
11	Jiawen Yi, Guo Chen	Decoupling SQL Query Hardness Parsing for Text-to-SQL.	CoRR	2023	DBLP DOI BibTeX RDF
11	Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, Kunihiro Wasa	On the hardness of inclusion-wise minimal separators enumeration.	CoRR	2023	DBLP DOI BibTeX RDF
11	Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi	Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.	CoRR	2023	DBLP DOI BibTeX RDF
11	Pasin Manurangsi	A Note on Hardness of Computing Recursive Teaching Dimension.	CoRR	2023	DBLP DOI BibTeX RDF
11	Hengzhao Ma, Jianzhong Li 0001, Xiangyu Gao	Optimization Problems on The Weighted Massively Parallel Computation Model: Hardness and Algorithms.	CoRR	2023	DBLP DOI BibTeX RDF
11	Tamás Sarlós, Xingyou Song, David P. Woodruff, Qiuyi Zhang 0001	Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products.	CoRR	2023	DBLP DOI BibTeX RDF
11	Will Perkins 0001, Yuzhou Wang	On the hardness of finding balanced independent sets in random bipartite graphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu, Angelos Pelecanos	On the Computational Hardness of Quantum One-Wayness.	CoRR	2023	DBLP DOI BibTeX RDF
11	Stephan Wäldchen	Hardness of Deceptive Certificate Selection.	CoRR	2023	DBLP DOI BibTeX RDF
11	Guilhem Gamard, Pierre Guillon 0001, Kévin Perrot, Guillaume Theyssier	Hardness of monadic second-order formulae over succinct graphs.	CoRR	2023	DBLP DOI BibTeX RDF
11	He Sun 0001, Danny Vagnozzi	Three Hardness Results for Graph Similarity Problems.	CoRR	2023	DBLP DOI BibTeX RDF
11	Elie Abboud, Noga Ron-Zewi	Finer-grained Reductions in Fine-grained Hardness of Approximation.	CoRR	2023	DBLP DOI BibTeX RDF