Search results for "NP-hardness"

Hits ?▲	Authors	Title	Venue	Year	Link
11	Charanjit S. Jutla, Chengyu Lin 0001	Enhancing Ring-LWE Hardness using Dedekind Index Theorem.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Krijn Reijnders, Simona Samardjiska, Monika Trimoska	Hardness estimates of the Code Equivalence Problem in the Rank Metric.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Alessandro Barenghi, Jean-François Biasse, Edoardo Persichetti, Paolo Santini	On the Computational Hardness of the Code Equivalence Problem in Cryptography.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Emanuele Bellini 0002, Rusydi H. Makarim, Carlo Sanna, Javier A. Verbel	An Estimator for the Hardness of the MQ Problem.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen	Entropic Hardness of Module-LWE from Module-NTRU.	IACR Cryptol. ePrint Arch.	2022	DBLP 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.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Gal Arnon, Alessandro Chiesa, Eylon Yogev	Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Marshall Ball, Dana Dachman-Soled, Julian Loss	(Nondeterministic) Hardness vs. Non-Malleability.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan	SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Paolo Santini, Marco Baldi, Franco Chiaraluce	Computational Hardness of the Permuted Kernel and Subcode Equivalence Problems.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Thomas Debris-Alazard, Nicolas Resch	Worst and Average Case Hardness of Decoding via Smoothing Bounds.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen	On the Hardness of Module Learning With Errors with Short Distributions.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Parker Newton, Silas Richelson	A Lower Bound for Proving Hardness of Learning with Rounding with Polynomial Modulus.	IACR Cryptol. ePrint Arch.	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.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Dipayan Das 0001, Antoine Joux	On the Hardness of the Finite Field Isomorphism Problem.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Shweta Agrawal, Simran Kumari, Anshu Yadav, Shota Yamada 0001	Trace and Revoke with Optimal Parameters from Polynomial Hardness.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Zvika Brakerski, Ran Canetti, Luowen Qian	On the computational hardness needed for quantum cryptography.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
11	Ming-Lo Wu, Emanuele Ripiccini, Ekin Kizilkan, Francesco Gramuglia, Pouyan Keshavarzian, Carlo Alberto Fenoglio, Kazuhiro Morimoto, Edoardo Charbon	Radiation Hardness Study of Single-Photon Avalanche Diode for Space and High Energy Physics Applications.	Sensors	2022	DBLP DOI BibTeX RDF
11	Konstantinos Papadopoulos 0001, Eleni Koustriava, Evangelia Georgoula, Vaia Kalpia	Individuals with and without Visual Impairments Use a Force Feedback Device to Identify the Friction and Hardness of Haptic Surfaces.	Sensors	2022	DBLP DOI BibTeX RDF
11	Peng Yang, Zhiguo Fu	Local holographic transformations: tractability and hardness.	Frontiers Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Yang Wang, Mingqiang Wang	On the hardness of NTRU problems.	Frontiers Comput. Sci.	2022	DBLP DOI BibTeX RDF
11	Xianpeng Wang 0002, Yao Wang, Lixin Tang	Strip Hardness Prediction in Continuous Annealing Using Multiobjective Sparse Nonlinear Ensemble Learning With Evolutionary Feature Selection.	IEEE Trans Autom. Sci. Eng.	2022	DBLP DOI BibTeX RDF
11	Alessio Mansutti	An auxiliary logic on trees: On the tower-hardness of logics featuring reachability and submodel reasoning.	Inf. Comput.	2022	DBLP DOI BibTeX RDF
11	Xingyu Yan, Lize Gu, Jingwen Suo, Licheng Wang	Leveraging the hardness of dihedral coset problem for quantum cryptography.	Quantum Inf. Process.	2022	DBLP DOI BibTeX RDF
11	Takeshi Tanabe, Kiyohiko Nunokawa, Kouki Doi, Shuichi Ino	Contribution of Vibration, Tapping Sound, and Reaction Force to Hardness Perception During Indirect Tapping Using a White Cane.	IEEE Trans. Haptics	2022	DBLP DOI BibTeX RDF
11	Di Yan, Hanlin Liu, Shuoyao Zhao, Yu Yu 0001	On the Hardness of Sparsely Learning Parity with Noise.	Comput. J.	2022	DBLP DOI BibTeX RDF
11	Daniel Gibney, Sharma V. Thankachan, Srinivas Aluru	On the Hardness of Sequence Alignment on De Bruijn Graphs.	J. Comput. Biol.	2022	DBLP DOI BibTeX RDF
11	Johannes Blum 0001	W[1]-hardness of the k-center problem parameterized by the skeleton dimension.	J. Comb. Optim.	2022	DBLP DOI BibTeX RDF
11	Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami	Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
11	Anne Broadbent, Alex Bredariol Grilo	QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
11	Zeyu Guo 0001, Mrinal Kumar 0001, Ramprasad Saptharishi, Noam Solomon	Derandomization from Algebraic Hardness.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
11	Julia Chuzhoy, David H. K. Kim, Rachit Nimavat	New Hardness Results for Routing on Disjoint Paths.	SIAM J. Comput.	2022	DBLP DOI BibTeX RDF
11	Tatiana Belova, Ivan Bliznets	Hardness of Approximation for H-Free Edge Modification Problems: Towards a Dichotomy.	ISAAC	2022	DBLP DOI BibTeX RDF
11	Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Sai Sandeep, Jakub Tarnawski, Yihao Zhang	On the Hardness of Scheduling With Non-Uniform Communication Delays.	SODA	2022	DBLP DOI BibTeX RDF
11	Marvin Künnemann, André Nusser	Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union.	SODA	2022	DBLP DOI BibTeX RDF
11	Thomas Chen, Xi Chen 0001, Binghui Peng, Mihalis Yannakakis	Computational Hardness of the Hylland-Zeckhauser Scheme.	SODA	2022	DBLP DOI BibTeX RDF
11	Fatemeh Esfahani, Venkatesh Srinivasan 0001, Alex Thomo, Kui Wu 0001	Nucleus Decomposition in Probabilistic Graphs: Hardness and Algorithms.	ICDE	2022	DBLP DOI BibTeX RDF
11	Quanpeng Jiang, Jie Feng 0003, Yuping Liang, Ziyu Zhou, Xiangrong Zhang, Licheng Jiao	Motion-Aligned and Hardness-Aware Dynamic Update Network for Weakly-Supervised Vehicle Detection in Satellite Videos.	IFIP TC12 ICIS	2022	DBLP DOI BibTeX RDF
11	Ronen Shaltiel, Emanuele Viola	On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization.	ITCS	2022	DBLP DOI BibTeX RDF
11	Huck Bennett, Chris Peikert, Yi Tang	Improved Hardness of BDD and SVP Under Gap-(S)ETH.	ITCS	2022	DBLP DOI BibTeX RDF
11	Lijie Chen 0001, Shuichi Hirahara, Neekon Vafa	Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions.	ITCS	2022	DBLP DOI BibTeX RDF
11	Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani	Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem.	ITCS	2022	DBLP DOI BibTeX RDF
11	B. S. Panda 0001, Sachin	Hardness and Approximation Results for Some Variants of Stable Marriage Problem.	CALDAM	2022	DBLP DOI BibTeX RDF
11	Irene Heinrich, Philine Schiewe, Constantin Seebach	Algorithms and Hardness for Non-Pool-Based Line Planning.	ATMOS	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.	WWW	2022	DBLP DOI BibTeX RDF
11	Aitor Godoy, Ismael Rodríguez, Fernando Rubio 0001	On the hardness of finding good pacts.	CEC	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.	CEC	2022	DBLP DOI BibTeX RDF
11	Shuichi Hirahara	NP-Hardness of Learning Programs and Partial MCSP.	FOCS	2022	DBLP DOI BibTeX RDF
11	Lijie Chen 0001, Ron D. Rothblum, Roei Tell	Unstructured Hardness to Average-Case Randomness.	FOCS	2022	DBLP DOI BibTeX RDF
11	Brice Huang, Mark Sellke	Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses.	FOCS	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.	FOCS	2022	DBLP DOI BibTeX RDF
11	Shuichi Hirahara, Nobutaka Shimizu	Hardness Self-Amplification from Feasible Hard-Core Sets.	FOCS	2022	DBLP DOI BibTeX RDF
11	Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein	Hardness of Token Swapping on Trees.	ESA	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.	ICALP	2022	DBLP DOI 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.	ICALP	2022	DBLP DOI BibTeX RDF
11	Tamir Bendory, Oscar Michelin, Amit Singer	Sparse Multi-Reference Alignment: Sample Complexity and Computational Hardness.	ICASSP	2022	DBLP DOI BibTeX RDF
11	Nicolas Grelier	Hardness and Approximation of Minimum Convex Partition.	SoCG	2022	DBLP DOI BibTeX RDF
11	Yutaka Nakanishi, Akihiro Matsuura	An Interactive Haptic Display System with Changeable Hardness Using Magneto-Rheological Fluid.	VRST	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.	NAACL-HLT (Findings)	2022	DBLP DOI BibTeX RDF
11	Timothy Stevens, Christian Skalka, Christelle Vincent, John Ring, Samuel Clark, Joseph P. Near	Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errors.	USENIX Security Symposium	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.	ACM Multimedia	2022	DBLP DOI BibTeX RDF
11	Aritra Konar, Nicholas D. Sidiropoulos	The Triangle-Densest-K-Subgraph Problem: Hardness, Lovász Extension, and Application to Document Summarization.	AAAI	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.	AAAI	2022	DBLP DOI BibTeX RDF
11	Raghunath Reddy Madireddy, Subhas C. Nandy, Supantha Pandit	Exact Algorithms and Hardness Results for Geometric Red-Blue Hitting Set Problem.	FAW	2022	DBLP DOI BibTeX RDF
11	Xuan Liu, Liwei Ci, Jianhua Zhang, Yan Zhao, K. M. Arafat Aziz	A granular jamming based hollow variable stiffness structure with adjustable local hardness.	ROBIO	2022	DBLP DOI BibTeX RDF
11	A. Chen Shilin, B. Shi Wei	Hardness indentation detection and classification technology based on image processing.	RCAR	2022	DBLP DOI BibTeX RDF
11	Jong-Ryul Lee, Yong-Hyuk Moon	On the Hardness of Pruning NASNet.	ICTC	2022	DBLP DOI BibTeX RDF
11	Dror Chawin, Ishay Haviv	Hardness of Linear Index Coding on Perturbed Instances.	Allerton	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.	EC	2022	DBLP DOI BibTeX RDF
11	Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta	Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness.	EC	2022	DBLP DOI BibTeX RDF
11	Robin Hirsch, Brett McLean	EXPTIME-hardness of higher-dimensional Minkowski spacetime.	AiML	2022	DBLP BibTeX RDF
11	Chris Brzuska, Geoffroy Couteau	On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness.	EUROCRYPT (2)	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.	CVPR	2022	DBLP DOI BibTeX RDF
11	Naghmeh Zamani, Heather Culbertson	Combining Haptic Augmented Reality with a Stylus-Based Encountered-Type Display to Modify Perceived Hardness.	HAPTICS	2022	DBLP DOI BibTeX RDF
11	Guang Zhao, Xianmin Liu, Hui Xie, Yuhang Xu, Salah Aldeen Abdo Alghurbani	The design of the tablet hardness tester.	ICMIP	2022	DBLP DOI BibTeX RDF
11	Shay Gershtein, Uri Avron, Ido Guy, Tova Milo, Slava Novgorodov	On the Hardness of Category Tree Construction.	ICDT	2022	DBLP DOI BibTeX RDF
11	Dimitar Karastoyanov, Nikolay Stoimenov	Innovative Approach for Obtaining Metal Parts with Improved Hardness and Wear Resistance.	CoDIT	2022	DBLP DOI BibTeX RDF
11	Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen	Entropic Hardness of Module-LWE from Module-NTRU.	INDOCRYPT	2022	DBLP DOI 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.	MICCAI (2)	2022	DBLP DOI 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.	EMNLP	2022	DBLP DOI BibTeX RDF
11	Xinran Zhao, Shikhar Murty, Christopher D. Manning	On Measuring the Intrinsic Few-Shot Hardness of Datasets.	EMNLP	2022	DBLP DOI BibTeX RDF
11	Radu Curticapean, Mingji Xia	Parameterizing the Permanent: Hardness for fixed excluded minors.	SOSA	2022	DBLP DOI BibTeX RDF
11	Rishi Saket	Algorithms and Hardness for Learning Linear Thresholds from Label Proportions.	NeurIPS	2022	DBLP BibTeX RDF
11	Michelangelo Conserva, Paulo E. Rauber	Hardness in Markov Decision Processes: Theory and Practice.	NeurIPS	2022	DBLP BibTeX RDF
11	Ilias Diakonikolas, Daniel Kane 0001, Pasin Manurangsi, Lisheng Ren	Cryptographic Hardness of Learning Halfspaces with Massart Noise.	NeurIPS	2022	DBLP BibTeX RDF
11	Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka	Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks.	NeurIPS	2022	DBLP BibTeX RDF
11	Ilias Diakonikolas, Daniel Kane 0001	Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise.	COLT	2022	DBLP BibTeX RDF
11	Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie 0002	Hardness of Maximum Likelihood Learning of DPPs.	COLT	2022	DBLP BibTeX RDF
11	Shahar Dobzinski, Shiri Ron, Jan Vondrák	On the hardness of dominant strategy mechanism design.	STOC	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.	STOC	2022	DBLP DOI BibTeX RDF
11	Sevag Gharibian, François Le Gall	Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture.	STOC	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.	STOC	2022	DBLP DOI BibTeX RDF
11	Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann	On the Hardness of Computing the Edit Distance of Shallow Trees.	SPIRE	2022	DBLP DOI BibTeX RDF
11	Daniel A. Spielman, Peng Zhang	Hardness Results for Weaver's Discrepancy Problem.	APPROX/RANDOM	2022	DBLP DOI BibTeX RDF
11	Emanuele Bellini 0002, Rusydi H. Makarim, Carlo Sanna, Javier A. Verbel	An Estimator for the Hardness of the MQ Problem.	AFRICACRYPT	2022	DBLP DOI BibTeX RDF
11	Marshall Ball, Dana Dachman-Soled, Julian Loss	(Nondeterministic) Hardness vs. Non-malleability.	CRYPTO (1)	2022	DBLP DOI BibTeX RDF
11	Sultan Nurmukhamedov, Artur Pak, Rustem Takhanov, Zhenisbek Assylbekov	Hardness of Learning AES Key (Short Paper).	DP@AI*IA	2022	DBLP BibTeX RDF
11	Ivan Bliznets, Danil Sagunov	Two Generalizations of Proper Coloring: Hardness and Approximability.	COCOON	2022	DBLP DOI BibTeX RDF
11	Ali Ahmadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi, Ðorde Zikelic	Algorithms and Hardness Results for Computing Cores of Markov Chains.	FSTTCS	2022	DBLP DOI BibTeX RDF
11	Radu Curticapean, Nutan Limaye, Srikanth Srinivasan 0001	On the VNP-Hardness of Some Monomial Symmetric Polynomials.	FSTTCS	2022	DBLP DOI BibTeX RDF