Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link
11	Eurinardo Rodrigues Costa, Nicolas Almeida Martins, Rudini M. Sampaio	Spy game: FPT-algorithm, hardness and graph products.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Debajyoti Mondal, Angelin Jemima Rajasingh, N. Parthiban, Indra Rajasingh	APX-hardness and approximation for the k-burning number problem.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Carlos V. G. C. Lima, Thiago Marcilon, Nicolas Almeida Martins, Rudini M. Sampaio	PSPACE-hardness of variants of the graph coloring game.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Julien Bensmail	On the hardness of determining the irregularity strength of graphs.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Priyanka Mukhopadhyay	The Projection Games Conjecture and the hardness of approximation of super-SAT and related problems.	J. Comput. Syst. Sci.	2022	DBLP DOI BibTeX RDF
11	Pedro Yuri Arbs Paiva, Camila Castro Moreno, Kate Smith-Miles, Maria Gabriela Valeriano, Ana Carolina Lorena	Relating instance hardness to classification performance in a dataset: a visual approach.	Mach. Learn.	2022	DBLP DOI BibTeX RDF
11	Lijie Chen 0001, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam	Beyond Natural Proofs: Hardness Magnification and Locality.	J. ACM	2022	DBLP DOI BibTeX RDF
11	Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman	Nearly Optimal Pseudorandomness from Hardness.	J. ACM	2022	DBLP DOI BibTeX RDF
11	Pasquale Antonante, Vasileios Tzoumas, Heng Yang 0002, Luca Carlone	Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and Applications.	IEEE Trans. Robotics	2022	DBLP DOI BibTeX RDF
11	Shuichi Hirahara	NP-Hardness of Learning Programs and Partial MCSP.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Lijie Chen 0001, Jiatu Li, Tianqi Yang 0001	Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie 0002	Hardness of Maximum Likelihood Learning of DPPs.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Lijie Chen 0001, Ron D. Rothblum, Roei Tell	Unstructured Hardness to Average-Case Randomness.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Yanyi Liu, Rafael Pass	Leakage-Resilient Hardness v.s. Randomness.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Eshan Chattopadhyay, Jyun-Jie Liao	Hardness against Linear Branching Programs and More.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Yanyi Liu, Rafael Pass	Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Marshall Ball, Dana Dachman-Soled, Julian Loss	(Nondeterministic) Hardness vs. Non-Malleability.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Radu Curticapean, Nutan Limaye, Srikanth Srinivasan 0001	On the VNP-hardness of Some Monomial Symmetric Polynomials.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Shuichi Hirahara, Nobutaka Shimizu	Hardness Self-Amplification from Feasible Hard-Core Sets.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Suryajith Chillara, Coral Grichener, Amir Shpilka	On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Hunter Monroe	Average-Case Hardness of Proving Tautologies and Theorems.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
11	Michelangelo Conserva, Paulo E. Rauber	Hardness in Markov Decision Processes: Theory and Practice.	CoRR	2022	DBLP DOI BibTeX RDF
11	Kai Wang 0057, Yu Liu 0035, Quan Z. Sheng	Swift and Sure: Hardness-aware Contrastive Learning for Low-dimensional Knowledge Graph Embeddings.	CoRR	2022	DBLP BibTeX RDF
11	Ngoc Dang Nguyen, Lan Du 0002, Wray L. Buntine, Changyou Chen, Richard Beare	Hardness-guided domain adaptation to recognise biomedical named entities under low-resource scenarios.	CoRR	2022	DBLP DOI BibTeX RDF
11	David Gamarnik, Cristopher Moore, Lenka Zdeborová	Disordered Systems Insights on Computational Hardness.	CoRR	2022	DBLP DOI BibTeX RDF
11	Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta	Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness.	CoRR	2022	DBLP DOI BibTeX RDF
11	Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu	Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV.	CoRR	2022	DBLP DOI BibTeX RDF
11	Eric Price 0001, Sandeep Silwal, Samson Zhou	Hardness and Algorithms for Robust and Sparse Optimization.	CoRR	2022	DBLP DOI BibTeX RDF
11	Stefan Tiegel	Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems.	CoRR	2022	DBLP DOI BibTeX RDF
11	Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi	Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses.	CoRR	2022	DBLP DOI BibTeX RDF
11	Andrew Fraser, Brian Lavallee, Blair D. Sullivan	Gerrymandering Trees: Parameterized Hardness.	CoRR	2022	DBLP DOI BibTeX RDF
11	Danny Hermelin, Yuval Itzhaki, Hendrik Molter, Dvir Shabtay	Hardness of Interval Scheduling on Unrelated Machines.	CoRR	2022	DBLP DOI BibTeX RDF
11	Xueqing Deng, Peng Wang, Xiaochen Lian, Shawn D. Newsam	NightLab: A Dual-level Architecture with Hardness Detection for Segmentation at Night.	CoRR	2022	DBLP DOI BibTeX RDF
11	Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka	Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks.	CoRR	2022	DBLP BibTeX RDF
11	Minki Hhan, Tomoyuki Morimae, Takashi Yamakawa	From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments.	CoRR	2022	DBLP DOI BibTeX RDF
11	Hu Fu 0001, Jiawei Li, Daogao Liu	Pandora Box Problem with Nonobligatory Inspection: Hardness and Improved Approximation Algorithms.	CoRR	2022	DBLP DOI BibTeX RDF
11	Anne Elorza, Leticia Hernando, José Antonio Lozano 0001	Transitions from P to NP-hardness: the case of the Linear Ordering Problem.	CoRR	2022	DBLP DOI BibTeX RDF
11	Emil Alkin	Hardness of almost embedding simplicial complexes in Rd, II.	CoRR	2022	DBLP DOI BibTeX RDF
11	Upendra Kapshikar, Srijita Kundu	Diagonal distance of quantum codes and hardness of the minimum distance problem.	CoRR	2022	DBLP DOI BibTeX RDF
11	Shujian Zhang, Chengyue Gong, Xingchao Liu, Pengcheng He, Weizhu Chen, Mingyuan Zhou	ALLSH: Active Learning Guided by Local Sensitivity and Hardness.	CoRR	2022	DBLP DOI BibTeX RDF
11	Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren	Cryptographic Hardness of Learning Halfspaces with Massart Noise.	CoRR	2022	DBLP DOI BibTeX RDF
11	Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie 0002	Hardness of Maximum Likelihood Learning of DPPs.	CoRR	2022	DBLP DOI BibTeX RDF
11	Huong Luu, Marek Chrobak	Better Hardness Results for the Minimum Spanning Tree Congestion Problem.	CoRR	2022	DBLP DOI BibTeX RDF
11	Robin Hirsch, Brett McLean	EXPTIME-hardness of higher-dimensional Minkowski spacetime.	CoRR	2022	DBLP DOI BibTeX RDF
11	Swaroop Mishra, Anjana Arunkumar, Chris Bryan, Chitta Baral	Hardness of Samples Need to be Quantified for a Reliable Evaluation System: Exploring Potential Opportunities with a New Task.	CoRR	2022	DBLP DOI BibTeX RDF
11	Giuseppe D'Alconzo	A Note on the Hardness of Problems from Cryptographic Group Actions.	CoRR	2022	DBLP BibTeX RDF
11	Alexander S. Kulikov, Ivan Mihajlin	Polynomial formulations as a barrier for reduction-based hardness proofs.	CoRR	2022	DBLP DOI BibTeX RDF
11	Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan R. Ullman, Lydia Zakynthinou	Multitask Learning via Shared Features: Algorithms and Hardness.	CoRR	2022	DBLP DOI BibTeX RDF
11	Daniel A. Spielman, Peng Zhang	Hardness Results for Weaver's Discrepancy Problem.	CoRR	2022	DBLP DOI BibTeX RDF
11	Houchen Zuo, Yongquan Jiang, Yan Yang 0001, Baoying Liu, Jie Hu	Hardness prediction of age-hardening aluminum alloy based on ensemble learning.	CoRR	2022	DBLP DOI BibTeX RDF
11	Hari Krovi	Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent.	CoRR	2022	DBLP DOI BibTeX RDF
11	Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang 0001	Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity.	CoRR	2022	DBLP BibTeX RDF
11	Ming Ding 0005, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang 0052	Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets.	CoRR	2022	DBLP BibTeX RDF
11	Minmin Liu, Xuechen Li, Xiangbo Gao, Junliang Chen, Linlin Shen, Huisi Wu	Sample hardness based gradient loss for long-tailed cervical cell detection.	CoRR	2022	DBLP DOI BibTeX RDF
11	Akshansh Mishra, Eyob Messele Sefene, Gopikrishna Nidigonda, Assefa Asmare Tsegaw	Performance Evaluation of Machine Learning-based Algorithm and Taguchi Algorithm for the Determination of the Hardness Value of the Friction Stir Welded AA 6262 Joints at a Nugget Zone.	CoRR	2022	DBLP DOI BibTeX RDF
11	Divesh Aggarwal, Rajendra Kumar 0002	Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms, and of the Subset Sum Problem!	CoRR	2022	DBLP DOI BibTeX RDF
11	Michael Skotnica, Martin Tancer	NP-hardness of computing PL geometric category in dimension 2.	CoRR	2022	DBLP DOI BibTeX RDF
11	Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen	Complexity Framework for Forbidden Subgraphs: When Hardness Is Not Preserved under Edge Subdivision.	CoRR	2022	DBLP DOI BibTeX RDF
11	Xinran Zhao, Shikhar Murty, Christopher D. Manning	On Measuring the Intrinsic Few-Shot Hardness of Datasets.	CoRR	2022	DBLP DOI BibTeX RDF
11	Andris Ambainis, Harry Buhrman, Koen Leijnse, Subhasree Patro, Florian Speelman	Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture.	CoRR	2022	DBLP DOI BibTeX RDF
11	Marcin Wrochna	A note on hardness of promise hypergraph colouring.	CoRR	2022	DBLP DOI BibTeX RDF
11	Suryajith Chillara, Coral Grichener, Amir Shpilka	On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts.	CoRR	2022	DBLP DOI BibTeX RDF
11	S. V. Ullas Chandran, Sandi Klavzar, P. K. Neethu, Rudini Menezes Sampaio	The general position avoidance game and hardness of general position games.	CoRR	2022	DBLP DOI BibTeX RDF
11	Brian Hu Zhang, Gabriele Farina, Andrea Celli, Tuomas Sandholm	Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation.	CoRR	2022	DBLP DOI BibTeX RDF
11	Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae	Improved Hardness Results for the Guided Local Hamiltonian Problem.	CoRR	2022	DBLP DOI BibTeX RDF
11	Zvika Brakerski, Ran Canetti, Luowen Qian	On the computational hardness needed for quantum cryptography.	CoRR	2022	DBLP DOI BibTeX RDF
11	Steven Heilman	Hyperstable Sets with Voting and Algorithmic Hardness Applications.	CoRR	2022	DBLP DOI BibTeX RDF
11	Haotian Ye, Xiaoyu Chen, Liwei Wang 0001, Simon S. Du	On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardness.	CoRR	2022	DBLP DOI BibTeX RDF
11	Hunter Monroe	Average-Case Hardness of Proving Tautologies and Theorems.	CoRR	2022	DBLP DOI BibTeX RDF
11	Matthew Ferland, Vikram Kher	NP-Hardness of a 2D, a 2.5D, and a 3D Puzzle Game.	CoRR	2022	DBLP BibTeX RDF
11	Chengming Xu 0001, Chen Liu, Siqian Yang, Yabiao Wang, Shijie Zhang, Lijie Jia, Yanwei Fu	Split-PU: Hardness-aware Training Strategy for Positive-Unlabeled Learning.	CoRR	2022	DBLP DOI BibTeX RDF
11	Hilal Asi, Karan N. Chadha, Gary Cheng 0004, John C. Duchi	Private optimization in the interpolation regime: faster rates and hardness results.	CoRR	2022	DBLP DOI BibTeX RDF
11	Mina Dalirrooyfard, Ce Jin 0001, Virginia Vassilevska Williams, Nicole Wein	Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles.	CoRR	2022	DBLP DOI BibTeX RDF
11	Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir	Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond.	CoRR	2022	DBLP DOI BibTeX RDF
11	Takashi Ishizuka, Naoyuki Kamiyama	NP-hardness of Computing Uniform Nash Equilibria on Planar Bimatrix Game.	CoRR	2022	DBLP DOI BibTeX RDF
11	Carl Feghali, Felicia Lucke, Daniël Paulusma, Bernard Ries	New Hardness Results for (Perfect) Matching Cut and Disconnected Perfect Matching.	CoRR	2022	DBLP DOI BibTeX RDF
11	Karl Bringmann, Nofar Carmeli	Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries.	CoRR	2022	DBLP DOI BibTeX RDF
11	Hadyn Tang	A Framework for Loop and Path Puzzle Satisfiability NP-Hardness Results.	CoRR	2022	DBLP BibTeX RDF
11	Peng Zhang	Hardness Results for Minimizing the Covariance of Randomly Signed Sum of Vectors.	CoRR	2022	DBLP DOI BibTeX RDF
11	John Haslegrave	Monitoring edge-geodetic sets: hardness and graph products.	CoRR	2022	DBLP DOI BibTeX RDF
11	Gustavo P. Torquette, Victor S. Nunes, Pedro Yuri Arbs Paiva, Lourenço B. C. Neto, Ana Carolina Lorena	Characterizing instance hardness in classification and regression problems.	CoRR	2022	DBLP DOI BibTeX RDF
11	Diptendu Chatterjee, Rishiraj Bhattacharyya	Firefighter Problem with Minimum Budget: Hardness and Approximation Algorithm for Unit Disk Graphs.	CoRR	2022	DBLP DOI BibTeX RDF
11	Shahar Dobzinski, Shiri Ron, Jan Vondrák	On the Hardness of Dominant Strategy Mechanism Design.	CoRR	2022	DBLP DOI BibTeX RDF
11	Alexander A. Semenov, Konstantin Chukharev, Egor Tarasov, Daniil Chivilikhin, Viktor Kondratiev	Estimating the hardness of SAT encodings for Logical Equivalence Checking of Boolean circuits.	CoRR	2022	DBLP DOI BibTeX RDF
11	Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi	Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs.	CoRR	2022	DBLP DOI BibTeX RDF
11	Angelos Chatzimparmpas, Fernando V. Paulovich, Andreas Kerren	HardVis: Visual Analytics to Handle Instance Hardness Using Undersampling and Oversampling Techniques.	CoRR	2022	DBLP DOI BibTeX RDF
11	Tzvika Geft, Dan Halperin	Refined Hardness of Distance-Optimal Multi-Agent Path Finding.	CoRR	2022	DBLP DOI BibTeX RDF
11	Debasis Dwibedy, Rakesh Mohanty	A Note on Hardness of Multiprocessor Scheduling with Scheduling Solution Space Tree.	CoRR	2022	DBLP BibTeX RDF
11	Huck Bennett, Chris Peikert	Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes.	CoRR	2022	DBLP BibTeX RDF
11	Mayank Chaturvedi, Bengt J. Nilsson	APX-Hardness of the Minimum Vision Points Problem.	CoRR	2022	DBLP DOI BibTeX RDF
11	Zeyang Zhang, Ziwei Zhang, Xin Wang 0019, Wenwu Zhu 0001	Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum.	CoRR	2022	DBLP DOI BibTeX RDF
11	Ranjan Pal, Peihan Liu, Taoan Lu, Ed Hua	How Hard Is Cyber-risk Management in IT/OT Systems? A Theory to Classify and Conquer Hardness of Insuring ICSs.	ACM Trans. Cyber Phys. Syst.	2022	DBLP DOI BibTeX RDF
11	B. S. Panda 0001, Pooja Goyal	Hardness results of global total k-domination problem in graphs.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
11	Alexandre Santiago de Abreu, Luís Felipe I. Cunha, Celina M. H. de Figueiredo, Franklin L. Marquezino, Daniel Posner, Renato Portugal	Total tessellation cover: Bounds, hardness, and applications.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
11	Aravind Gollakota, Daniel Liang	On the Hardness of PAC-learning Stabilizer States with Noise.	Quantum	2022	DBLP DOI BibTeX RDF
11	Abhijit Saha, Subhas Chandra Mondal	Modelling bead width and bead hardness in submerged arc welding using dimensional analysis.	Int. J. Manuf. Technol. Manag.	2022	DBLP DOI BibTeX RDF
11	Eugen Czeizler, Alexandru Popa 0001, Victor Popescu	Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem.	Sci. Ann. Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Denis Ariel Avila-Salgado, Arturo Juárez-Hernández, María Lara Banda, Arnoldo Bedolla-Jacuinde, Francisco V. Guerra	Effects of Nb Additions and Heat Treatments on the Microstructure, Hardness and Wear Resistance of CuNiCrSiCoTiNbx High-Entropy Alloys.	Entropy	2022	DBLP DOI BibTeX RDF
11		Code Equivalence in the Sum-Rank Metric: Hardness and Completeness.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Geng Wang, Wenwen Xia, Gongyu Shi, Ming Wan, Yuncong Zhang, Dawu Gu	Revisiting the Concrete Hardness of SelfTargetMSIS in CRYSTALS-Dilithium.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF